백준 문제집 풀이 7 - 스택의 활용
백준 BaaaaaaaaaaarkingDog님이 제작하신 문제집을 사용합니다
링크 : https://www.acmicpc.net/workbook/view/7312
문제집: 0x08강 - 스택의 활용(수식의 괄호 쌍) (BaaaaaaaaaaarkingDog)
www.acmicpc.net
무너져버린 코테 기초를 다시 쌓기 위해 유형별로 문제를 쭉쭉 밀기로 했다.
모든 문제를 풀고 필요할 경우 코멘트를 작성한다.
괄호식 계산의 알고리즘은 다음과 같다.
- 여는 괄호 (가 입력될 경우, 스택에 여는 괄호를 push한다.
- 닫는 괄호 )가 입력될 경우, 스택에서 여는 괄호를 pop한다. 스택에 여는 괄호가 없으면 유효하지 않은 괄호식이다.
- 마지막까지 확인했을 때 스택에 여는 괄호가 남아있으면 유효하지 않은 괄호식이다.
다음 문제들은 이 기본 알고리즘을 응용해 풀 수 있다.
4949번 : 균형잡힌 세상 → string 변수 str에 줄 전체를 저장하기 위해 getline(cin, str)을 사용하자.
기본 괄호식 계산에 더하여, 닫는 괄호가 입력됐을 때 닫는 괄호와 스택의 top이 다를 경우 유효하지 않은 괄호식이다.
3986번 : 좋은 단어 → A와 B가 입력된 횟수를 카운팅한다. 홀수 번 입력됐으면 여는 괄호(문자), 짝수 번 입력됐으면 닫는 괄호(문자)로 간주한다. 위의 문제와 동일하게 풀 수 있다.
9012번 : 괄호 → 코멘트 없음
10799번 : 쇠막대기 → 일단 인접한 괄호열 ()을 식별해야한다. 나는 last 변수를 사용해 이전 문자를 기록했다.
레이저를 만났을 경우 현재 스택에 있는 모든 막대기들이 각각 하나의 조각을 생성한다. 막대기의 끝에 도달했을 경우, 즉 닫는 괄호를 만났을 경우 막대기의 아직 잘리지 않은 끝 부분이 하나의 조각이 된다.
2504번 : 괄호의 값 → 괄호식의 값을 계산하기 위해 정수를 저장하는 또다른 스택을 사용해야 한다. 이 스택 temp의 각 원소는 해당 여는 괄호로 시작된 괄호식의 값을 나타낸다.
여는 괄호를 만나면 새로운 괄호식이 생성되므로 temp에 0을 push한다. 닫는 괄호를 만나면 top을 갱신하고, 현재 top에 해당하는 괄호식이 끝났으므로 top의 값을 다음 top에 더한다.
풀이
그림으로 보는게 더 이해가 쉽다. 예제 입력에 대한 스택의 작동 과정을 확인해보자.
여는 괄호를 만나면 0을 push한다. 괄호가 닫히면 괄호열의 종류에 따라 top을 갱신한다. 이 경우 인접한 괄호열 ()이므로 top을 2로 갱신한다. 갱신을 마치면 그 값을 다음 top으로 전달한다.
마지막 단계에서 복합 괄호열 [X]를 만났으므로 top에 3을 곱해준다. 이후는 동일하게 그 값을 다음 top으로 전달한다. 이후 과정은 똑똑한 여러분의 상상에 맡긴다.
단, 이런 식으로 진행하면 끝까지 계산을 마쳤을 경우 temp 스택이 비어버린다. 당장 위의 예시에서도 다음 닫는 괄호를 처리하면 11 * 2 = 22가 pop되면서 스택이 비어버린다. 따라서 최종 결과값을 저장하기 위해서는 맨 처음에 스택에 0을 push 해둬야 한다.
푼 문제 : 5/5
총 소요 시간 : 50분