[자료구조][백준] 스택의 활용 | 백준 9012번 풀이

스택은 후입선출, LIFO(Last In First Out)구조이다.

이 스택을 활용할 수 있는 예시는

• 웹 브라우저 뒤로 가기) : 가장 나중에 열린 페이지부터 뒤로가기
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행 취소
• 괄호 검사

등이 있다.

 

 

백준 9012번 문제 '괄호'는 올바른 괄호 문자열(Valid PS, VPS)을 찾는 문제이다.

이 문제는 스택 자료구조를 활용하면 쉽게 풀 수 있다.

 

알고리즘 전공 강의를 열심히 들은 보람이 있다. 들은지 몇달이 지났는데, 기억이 나네

 

def P9012():
    num = int(input())
    vps = list(input() for _ in range(num))
    stack = []

    for string in vps:
        try:
            for char in string:
                if char == '(':
                    stack.append(0)
                elif char == ')':
                    stack.pop()

        except IndexError:
            print('NO')
            continue

        print('NO' if stack else 'YES')
        stack.clear()


if __name__ == '__main__':
    P9012()

위 코드는 이를 파이썬으로 구현한 것이다. 

 

'(' 일 때는 리스트에 임의의 요소를 추가하고,

')' 일 때는 리스트의 마지막 요소를 꺼내는 방식으로 스택을 구현했다

 

그리고, 예외처리를 걸어 빈 리스트에서 요소를 꺼내려 할 때, 즉 vps가 성립하지 않을 때 'NO'를 출력하고

예외처리 구문을 통과한 후에도 스택에 요소가 있으면 'NO'를 출력하게 짰다.

 

예외처리 구문을 통과하고, 스택에 남은 요소가 없을 때. 즉, vps가 성립했을 때만 'YES'를 출력한다.