백준 - 9012. 괄호(MJ)

#9012. 괄호

백준 사이트의 실버 4티어인 문제이다. 이번 문제는 ‘단계별 문제풀기’에서 스택에 있는 문제를 가져왔다. 자료구조를 탄탄히 해야 할 것 같아서 스택의 기초가 되는 문제를 가져왔다.

📖Problem

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다.

그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다.

만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다.

예)

(())()와 ((())) 는 VPS 이지만

(()(, (())())) , (() 는 모두 VPS 가 아닌 문자열이다.

입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

Input

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

Output

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

****Example 1****

Input>>
**6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

Output>>**
NO
NO
YES
NO
YES
NO

Example 2

**Input >>**
**3
((
))
())(()

Output>>**
NO
NO
NO

🔍Approach

• 유형 : 자료구조의 ‘스택’

→ 그렇게 생각한 이유

단계별 문제의 ‘스택’파트에 있기도 했지만 짝이 맞으면 맞다고 판별하기 위해서는 count 변수로 개수를 세거나 짝이 맞을 때 pop을 하여 판별할 수 있다고 생각했다. pop하면 스택이 가장 먼저 떠오르기 때문에 스택을 사용하였다.

참고 사이트

1. 여는괄호와 닫는 괄호가 올바른 경우

예시 : ( ( ) ( ) ) ( ( ( ) ) )

→ 괄호의 짝이 딱 맞아떨어지는 경우, 최종적으로는 stack에 아무것도 남지 않게 된다. 따라서 입력 문자열을 다 확인한 후에 stack이 비어있다면 “YES”를 출력한다.

2. 괄호가 남는 경우 (= 여는 괄호가 많은 경우)

예시 : ( ( ( ( ) ( ) ) ( )

→ 이처럼 여는 괄호가 더 많을 경우에는 최종적으로 stack에 괄호가 남아있게 된다. 따라서, 입력받은 문자열을 다 확인하고 나서도 stack에 남아있는 경우에는 짝이 맞지 않는 것이므로 “NO”를 출력한다.

3. 괄호가 부족한 경우 (= 닫는 괄호가 많은 경우)

예시 : ( ( ) ) ( ) )

→ 닫는 괄호가 들어오면 stack에 담아둔 여는 괄호를 pop해야 하는데, 닫는 괄호가 더 많을 경우에는 pop할 괄호가 stack에 남아있지 않다. 위 그림처럼 stack은 빈 상태가 된다. 따라서 )이 들어왔을 때 stack이 비어있는지 확인해야 한다. 비어있다면 “NO”를 출력하고, 비어있지 않다면 pop을 하면 된다.

위 그림에 따라 풀이과정을 정리하면 아래와 같다.

• 풀이과정
  1. (일때, stack에 push
  2. ) 일때
     • stack이 비어있지 않다면 pop
     • stack이 비어있다면 “NO” print
  3. 입력받은 문자열 확인을 모두 마친 경우
     • stack이 비어있는 경우 “YES” print
     • stack이 비어있지 않은 경우 “NO” print

이 3가지 경우를 토대로 조건문을 걸어주어 코드로 구현한다.

🔍🔍Implement

정석 - stack

T = int(input())

for i in range(T):
    stack = []
    a = input()
    for j in a:
        if j == '(':
            stack.append(j)
        elif j == ')':
            if stack:
                stack.pop()
            else: # 스택에 괄호가 없을경우 NO
                print("NO")
                break
    else: # break문으로 끊기지 않고 수행됬을경우 수행한다
        if not stack: # break문으로 안끊기고 스택이 비어있다면 괄호가 다 맞는거다.
            print("YES")
        else: # break안 걸렸더라도 스택에 괄호가 들어있다면 NO이다.
            print("NO")

• ( 괄호가 들어오면 stack에 넣어준다.
• ) 괄호가 들어왔을때는 stack을 검사해 비어있다면 NO를 출력하고 break해주고 만약 비어있지 않다면 pop()을 한번 해준다.
• for-else 문으로 for문에서 한번도 break가 실행된 적이 없다면 else문을 실행한다. 하지만 그럴경우 stack이 비어있다면 괄호가 모두 짝이 맞은 경우이기 때문에 YES를 출력한다.
• else 문이 실행해도 스택안에 괄호가 남아있다면 짝이 안맞는 것이기 때문에 NO를 출력한다.

정석 X - count

정석은 stack이지만 굳이 stack을 사용하지 않고도 코드로 구현할 수 있다. 하지만 이러한 방식은 ()뿐 아니라 다른 종류의 괄호가 들어왔을 때 사용하기 어려운 방법이므로 최대한 자제해야 하는 방식이다.

n = int(input())
for _ in range(n):
    brackets = list(input())
    count = 0
    for b in brackets:
        if b == '(':
            count +=1
        elif b == ')':
            count -=1
        # count는 항상 0과 같거나 0보다 커야함. /'('가 먼저 나와야 하므로
        if count < 0:
            break
    if count == 0:
        print("YES")
    else:
        print("NO")

1. 괄호 리스트 : brackets 생성
2. brackets for문에서 값이 ‘(‘일 때, count += 1 / 값이 ‘)’일 때, count -= 1
3. 올바른 괄호 VPS가 되기 위한 조건이 ‘(‘가 먼저 나오고 짝이 맞아야 하므로 count의 값이 0보다 작으면 “NO”
4. 값이 0으로 딱 맞으면 “YES”

---

💡Remembrance

• 처음엔 괄호가 들어오면 count를 세는 것은 생각이 들었으나 최대한 stack을 이용해보려고 고민했다. 하지만 떠오르지 않았다. 어떻게 들어오고 뭐가 들어오고가 헷갈렸다. stack에서 push되고 pop되는 조건을 설정하는 것도 헷갈렸다.
• stack에서는 언제 무엇을 push할지, 언제 pop할지를 정확히 이해한 후에 코드를 구현해야 한다.