백준 9012번: 괄호

문제

• https://www.acmicpc.net/problem/9012
• 스택을 활용해 탐색 범위 줄이기 (계속 탐색할 필요성이 있는 값만 남기기)

기록 포인트

• 스택이나 큐를 활용하는 핵심 또한 탐색 범위를 효과적으로 관리하기 위해서다!
  • "스택을 사용하니 문제가 풀리네."가 아니라,
  • "스택을 사용해 불필요한 탐색을 줄이고 있구나!"로 문제를 정확히 이해하기
• 특정 자료구조로 탐색 대상을 정리하여 탐색 범위를 줄일 수 있는 상황 기억하기
  • 정렬되어 있지 않은 대상을 반복적으로 탐색할 때,
  • 일반 배열 대신 스택이나 큐와 같은 자료구조를 사용해
  • 반복의 다음 회차에서 탐색할 필요가 없는 값을 제거하는 방식으로
  • 탐색 범위를 줄일 수 있음

접근 방식

주먹구구의 해

• "("를 여는 괄호, ")"를 닫는 괄호라고 할 때,
• 각 여는 괄호에 대해 매칭되는 닫는 괄호(혹은 각 닫는 괄호에 대해 매칭되는 여는 괄호)를 찾아 매칭되지 않는 괄호가 없는지 확인해주어야 함

스택 활용

• 문제가 "( ( ( ) ) ( ) )" 라고 할 때,
• 주먹구구식으로 푼다면 가령, 맨 마지막의 ")"가 누구와 매칭되는지 찾기 위해 모든 "("를 확인해주어야 함
• 하지만 이미 다른 ")"와 매칭이 된 "("는 확인할 필요가 없음
• 그러므로 스택을 사용해 중간에 매칭이 되어 더 이상 탐색할 필요가 없는 항목은 제거해 줄 수 있고, 결과적으로 탐색의 범위가 줄어듦

제출 답안

스택 활용

import sys
N = int(sys.stdin.readline())
for i in range(N):
    # 괄호 문자열 확인
    target = sys.stdin.readline().rstrip()
    # 스택 생성
    stack = []
    is_valid = True
    # 각 문자열에 대한 탐색
    for c in target:
        # '여는 괄호'인 경우, 탐색 범위(스택)에 추가
        if c == "(": 
            stack.append(c)
            continue
        # '닫는 괄호'인데, 스택이 비어 있는 경우 (즉, 매칭할 '여는 괄호'가 없는 경우)
        if len(stack) == 0:
            is_valid = False
            break
        # 이번 '닫는 괄호'와 매칭되는 '여는 괄호'를 탐색 범위에서 제외
        # (이에 따라 다음에 등장하는 '닫는 괄호'는 이미 매칭된 '여는 괄호'를 탐색할 필요가 없음)
        stack.pop()
        
    # 매칭되지 않은 '여는 괄호'가 탐색 범위에 남아 있는지 확인
    if len(stack) > 0:
        is_valid = False
        
    if is_valid: 
        print("YES")
    else: 
        print("NO")

(참고) 단순화한 답안

import sys
N = int(sys.stdin.readline())
for i in range(N):
    target = sys.stdin.readline().rstrip()
    stack = 0
    for c in target:
        if c == "(": 
            stack += 1
        else: 
            stack -= 1
        if stack < 0:
            break
    if stack == 0: print("YES")
    else: print("NO")