[백준] 9012번: 괄호 python

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

9012번: 괄호

 

설계 방법

나의 방법

• ps가 주어졌을 때 “(”면 stack에 넣고 “)”면 stack에서 빼주었음
• “)”인데 stack에서 뺄 게 없으면 vps가 아닌거고, ps를 모두 돌고 나서도 (가 남아있어도 vps가 아님

다른 방법

• 꼭 stack을 이용하지 않더라도 sum = 0 이라고 선언 하여 구현할 수 있음
• “(”면 sum +=1, “)” 이면 sum -=1 이런 식으로

 

코드

# 내 코드 
# 스택 자료구조를 이용한 풀이 
N = int(input())

for _ in range(N):
  ps = list(input())
  stack = []
  ans = ''
  for i in ps:
    if i == "(":
      stack.append(i)
    elif i == ")":
      if len(stack) == 0:
        # print("NO")
        ans = 'no'
        break
      else:
        stack.pop()
  if len(stack) == 0 and ans != 'no':
    print('YES')
  else:
    print('NO')

# sum을 이용한 풀이 
a = int(input())

for i in range(a):
    b = input()
    s = list(b)
    sum = 0
    for i in s:
        if i == '(':
            sum += 1
        elif i == ')':
            sum -= 1
        if sum < 0:
            print('NO')
            break
    if sum > 0:
        print('NO')
    elif sum == 0:
        print('YES')

 

시간 복잡도

$O(n^2)$

 

어려웠던 점

• “)”인데 stack에서 뺄 게 없으면 break를 하고 stack의 길이로 ‘ps를 모두 돌고 나서도 (가 남아있어도 vps가 아님’ 의 경우를 작성하려고 하니 print가 2번 출력되는 현상이 나타났다
• 일단 나는 ans라는 변수를 만들어서 ans가 빈 배열인 경우에만 아래의 if문이 실행되도록 하였는데 아래의 예시를 보니 for j 와 같은 라인에 else를 하니 break문으로 끊어지지 않고 수행되었을 경우 수행하도록 할 수 있은 것을 확인 할 수 있었다
• break에 대해 좀 더 알아봐야 할 것 같다

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")

 

참고 자료

https://pacific-ocean.tistory.com/70

https://wookcode.tistory.com/49