[Algorithm][Python] 백준(BOJ) 9012 괄호

[문제]

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

---

[내 코드]

import sys

n = int(sys.stdin.readline())

stack = []

for _ in range(n):
    ps = sys.stdin.readline().strip()
    ps = list(ps)
    if len(ps) %2 == 1: # 총 개수 홀수면 바로 NO
        print("NO")
    else: 
        for i in range(len(ps)):
            if ps[i] == "(":
                ps[i] = -1
            else: 
                ps[i] = 1
        for x in ps:
            if (not bool(stack)): #stack 비어있으면
                stack.append(int(x))
            else:
                if(stack[-1] + int(x) == 0):
                    stack.pop()
                else:
                    stack.append(int(x))
        if (not bool(stack)): 
            print("YES")
        else:
            print("NO")

💡 아이디어

1. 개수의 합이 홀수이면 다른 조건 필요없이 NO 출력
2. ( 을 -1로 )를 +1 로 값을 바꾸고 합이 0일때 stack에서 POP을 시킨다.
3. 최종 stack이 비면 YES 출력

❌ 틀림

1. 여러 예시 한번에 돌리면 답이 틀림, 하나씩 돌리면 답 맞게 나옴
   stack을 for문 한번 돌면 비워줘야함 or stack을 for문 안에서 선언
2. 위의 식으로 풀었을 경우의 예외 –> ())(() NO 인데 YES로 출력됨
   위의 식은 ( ), ) ( 모두 가능하게 푼 방법임 –> 조건 수정 필요

#### 해결
import sys

n = int(sys.stdin.readline())

for _ in range(n):
    stack = [] ##수정

    ps = sys.stdin.readline().strip()
    ps = list(ps)
    if len(ps) %2 == 1: # 총 개수 홀수면 바로 NO
        print("NO")
    else: 
        for i in range(len(ps)):
            if ps[i] == "(":
                ps[i] = -1
            else: 
                ps[i] = 1
        for x in ps:
            if (not bool(stack)): #stack 비어있으면
                stack.append(int(x))
            else:
                if (stack[-1] == -1 and int(x) == 1): ##수정
                    stack.pop()
                else:
                    stack.append(int(x))
        if (not bool(stack)): 
            print("YES")
        else:
            print("NO")

⭕️ 해결

1. for문 안에 stack 선언
2. ’(‘ 나온 후 ‘)’ 나오면 POP 하도록 조건 수정

---

[다른 사람 코드]

import sys

T = int(sys.stdin.readline())

for i in range(T):
    stack = list(sys.stdin.readline().rstrip())
    sum = 0
    for target in stack:
        if target == '(':
            sum += 1
        elif target == ')':
            sum -= 1
        if sum < 0:
            print("NO")
            break
    if sum == 0:
        print("YES")
    else:
        print("NO")

💡 풀이

1. 결과적으로 ‘(‘와 ‘)’의 개수는 같아야한다.
2. ’(‘ 가 ‘)’보다 먼저 나와야한다.