문제 링크
- https://www.acmicpc.net/problem/9012
문제 출처
- 2012 ACM-ICPC 대전 인터넷 예선 G번
사용 알고리즘
- 스택
시간복잡도
- O(Tn)
풀이
괄호 짝 관련 문제는 경우의 수를 구하지 않는 이상 스택 구조를 사용하는 경우가 많습니다.
이 문제도 스택을 이용해 풀어봅시다.
백준 9012같은 문제는 여는 괄호는 push하고, 닫는 괄호가 나오면 pop을 해가며 푸는 것이 일반적입니다.
이 문제의 해결법은 간단합니다.
위에서 말한 대로
“여는 괄호는 push, 닫는 괄호는 pop을 해서 마지막에 size가 0이 되면 true, 0이 아니면 false다.”
라고 생각하기 쉽지만, 사실은 한 가지 조건이 더 추가가 됩니다.
underflow가 일어나면, 즉 열린 괄호는 없는데 닫으려고 하는 경우에도 false가 됩니다.
여는 괄호가 나오면 push하고
닫는 괄호가 나오면 pop을 하는데 중간에 underflow가 발생하면 false가 되고
모든 괄호를 다 처리 했을 때 스택의 size가 0이면 true, 0이 아니면 false입니다.
전체 코드
1 |
|