[백준] 9012 괄호 python 알고리즘 문제

문제 9012. 괄호

1. 나의 코드와 발상 과정

### 오답
from collections import deque
queue = deque()
n = int(input())
vps_list = list()
ans_list = []
for i in range(n):
    vps_list.append(deque(input()))

for vps in vps_list:
    if len(vps) % 2 != 0 or vps[0] == ')':
        ans_list.append('NO')
        continue
    else:
        while True:
            if len(vps) == 0:
                ans_list.append('YES')
                break
            if vps[-2] == '(' and vps[-1] == ')':
                vps.pop()
                vps.pop()
            else:
                vps.rotate(1)
                if len(vps) == 1:
                    ans_list.append('NO')
                    break
                elif len(vps) == 2 and vps[-2] == '(' and vps[-1] == '(':
                    ans_list.append('NO')
                    break
                elif len(vps) == 2 and vps[-2] == ')' and vps[-1] == ')':
                    ans_list.append('NO')
                    break

for i in ans_list:
    print(i)

답을 맞추지는 못했다.

일단 '열고' '닫고'가 제대로 쌍이 맞춰져있는지를 확인해보고, 그 리스트 안에서 무엇인가를 해결하려고 했던 것이 문제였던 것 같다.

 

일단 첫 시작부터 ')'가 나오거나 문자열의 길이가 홀수라면 vps 할아버지가 와도 괄호쌍이 완벽하게 만들어지지 않기 때문에 NO를 정답리스트에 넣고, 그 다음 문자열을 판별하는 식으로 if 단을 구성했다.

 

else 단은 자동적으로 문자열 길이가 짝수이고, '('로 시작한다.

여기서 부터 생각이 꼬이기 시작했는데, rotate 개념을 생각해서 맨 오른편의 원소 두가지가 () 쌍이면 pop으로 빼고 len이 0이나 1이 될 때까지 반복을 돌리는 것을 생각했다. 어쨌든 열고닫고 하는 것이 5번이 나와야 vps가 성립하기 때문이다.

 

그러나 스택 문제를 큐로 생각하여 푼 오류로 인해 결국 답을 맞추지 못했다.

 

2. 고수님의 깔끔한 코딩

 

(1) 정수를 스택처럼 구현한 코드

# 열고 닫고의 쌍의 개수를 sum으로 판별하여 출력해줌

a = int(input())
ans_list = []
for i in range(a):
    b = list(input())
    sum = 0
    for i in b:
        if i == '(':
            sum += 1
        elif i == ')':
            sum -= 1
        if sum < 0:
            ans_list.append('NO')
            break
    if sum > 0:
        ans_list.append('NO')
    elif sum == 0:
        ans_list.append('YES')

for i in ans_list:
    print(i)

b를 리스트로 받은 다음에, 이를 반복문을 사용해서 '('와 ')'에 따라 sum을 더하거나 빼주고 있다.

2중 for문 안의 if문은 '('가 있으면 +1을 해주고, ')'가 있으면 -1을 해준다. 반복문 안에서 sum이 -가 된다면,

)))((가 되는 것이기에 빠르게 반복문을 탈출해준다. 여기에서 양수가 될 때 break하지 않는 것은, '('가 나온 후 ')'가 나와야

하고, 반복문 안에서 sum은 양수가 되었다가 '0'이 되어야 YES를 출력할 수 있기 때문이다.

 

그렇기에 1차 for문 안에서 양수인지를 파악해주고 NO를 ans_list로 넣어주는 것이다. 만약 sum이 0이라면, 완벽한 vps쌍이기에 YES를 넣어준다.

 

직접 스택을 구현을 하지는 않았지만, 스택 구현과 비슷한 논리를 정수를 통해 활용하고 있는 모습이다.

괄호가 하나일 때는 구현하기 쉽겠지만, 대괄호까지 나오는 문제라면 활용하기는 힘든 것이라고 생각된다.

 

 

(2) 스택 자체를 구현한 코드

## append와 pop을 활용
num = int(input())

for i in range(num):
  input_data = input()
  bracket = []

  for j in input_data:
    if j == "(":
      bracket.append(j)
    elif j == ")":
      if len(bracket) != 0 and bracket[-1] == "(":
        bracket.pop()
      else:
        bracket.append(")")
        break

  if len(bracket) == 0:
    print("YES")
  else:
    print("NO")

정석적으로 bracket이라는 하나의 리스트 안에 (를 채워넣고, 만약 ')'가 bracket에 들어가야 할 때, bracket 제일 오른쪽에 있는 원소가 '('일 때, 그 '('를 pop()하는 구조를 가진다.

 

스택을 활용하여 짠 코드로 정석적인 코드 같다.

 

 

3. 아쉬운 점

이 괄호 문제를 풀고 나머지 스택문제를 풀어서 쉽게 해결되는 이점을 얻었다. 

하지만, 이 괄호 문제는 2시간 넘게 고민을 해도 풀지 못했다.

먼저 스택, 큐, 덱 같은 기본문제를 먼저 풀고 했으면 더 재미있게 풀었을 것 같다.

 

 

 

 

문제 출처:

https://www.acmicpc.net/problem/9012