백준 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")
Author And Source
이 문제에 관하여(백준 9012번: 괄호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@johnny/beak-9012저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)