스택
[BOJ] 1918 후위 표기식 (Python / 파이썬)
[BOJ] 1918 후위 표기식 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/1918 주어진 중위 표기식(infix)을 후위 표기식(postfix)로 바꾸는 문제이다. 문제에 나와있다시피 연산자의 우선순위에 따라 스택에서 push, pop의 과정을 통해 해결할 수 있다. 🛠 풀이 이 문제의 중요한 포인트는 연산자의 우선순위를 비교할 때, 우선순위가 같다면 stack안에 들어있는, 즉 식에서 왼쪽에 위치한 연산자를 처리해준다는 것이다. Step 1. expression리스트를 처음부터 한 문자씩 탐색한다. expression[i]가 알파벳이라면 res라는 결과 리스트에 append해준다. Step 2. expression[i]가 알파벳이 아니고 연산자라면 우선순위에 맞게 처리를 해준다. expression[i]가 (..
[BOJ] 10799 쇠막대기 (Python / 파이썬)
[BOJ] 10799 쇠막대기 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/10799 입력으로 주어진 괄호의 쌍을 분석하여 쇠막대기가 레이저에 의해 몇 개의 조각으로 잘려지는지 알아보는 문제이다. 🛠 풀이 이 문제는 스택을 이용하여 해결할 수 있는 문제이다. Step 1. 입력으로 주어진 쇠막대기와 레이저의 배치를 pipes로 받고 for문을 이용해 앞에서부터 탐색을 시작한다. (를 만나면 stack에 push해준다. Step 2. )를 만나면 pipes의 바로 전 인덱스를 살펴보고 만약 pipes[i-1]이 (라면 레이저이기 때문에 stack에서 pop해주고 res에 stack의 길이만큼 더해준다. 그렇지 않고 pipes[i-1]이 )라면 해당 라인의 막대기가 끝나는 지점이기 때문에 res에 1을 더해준다. 처..
[BOJ] 1874 스택수열 (Python / 파이썬)
[BOJ] 1874 스택수열 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/1874 1부터 n까지의 수를 스택에 넣고 빼는 것을 반복하는데, 오름차순으로만 push할 수 있고 임의의 수열이 주어졌을 때 위의 스택을 이용하여 만들 수 있는지 없는지를 알아보는 문제이다. 🛠 풀이 이 문제를 풀 때 처음에는 문제 자체를 이해하는데 어려움이 있었지만 아래에 있는 예제를 직접 손으로 그려가면서 이해할 수 있었다. Step 1. 1부터 n까지의 수를 넣어줄 sequence리스트와 결과로 보여줄 res리스트를 만들었다. 그리고 num변수를 1로 초기화하고 문제 조건과 비교할 수 있는 check변수를 True로 설정한 후에 임의의 수열을 만들 수 없다면 NO를 출력할 수 있도록 만들었다. Step 2. n개의 줄을 통해 입력되..