백준 9012번 : 괄호 [Python]

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

9012번: 괄호

문제

 

틀린 코드

N = int(input())

for i in range(N):
    PS = input()
    if PS.count("(") == PS.count(")") :
        print("YES")
    else :
        print("NO")

처음엔 이렇게 (와 )의 개수만 맞으면 된다고 간단하게 생각했었는데

(()))(

이러한 반례가 있다. ( 괄호의 개수는 같지만 닫힌 상태가 아님)

 

다시 도전 !

 

전체 코드

N = int(input())

for i in range(N):
    PS = input()
    stack = list(PS)
    if stack.count("(") == stack.count(")") :
        while True:
            index_close = stack.index(")")
            index_open = stack.index("(")
            if index_open < index_close :
                del stack[index_open]
                del stack[index_close - 1]
                if len(stack) == 0 :
                    print("YES")
                    break
            else :
                print("NO")
                break
    else :
        print("NO")

풀이설명

1. 앞서 말했듯이 (와 )의 개수를 이용하여 한번 걸러준다.

2. () 이렇게 되려면 ")"의 인덱스보다 "("의 인덱스 번호가 앞쪽에 위치해야 한다. 

    그러므로 두 인덱스를 비교하여 ")" 인덱스 > "(" 인덱스 이면 () 한쌍이 되므로 이 둘은 리스트에서 삭제해 준다.

    (💥이때, 삭제를 두 번 진행하므로 index_open이 삭제되면 리스트가 앞으로 한 칸씩 당겨오게 되므로 index_close 값을 -1 해주어 알맞은 인덱스를 삭제할 수 있도록 한다.)

    삭제한 후 리스트의 길이가 0이면 모두 () 짝을 맞추었다는 의미이므로 YES 출력

  ☝️ 위의 과정을 반복해 주면 된다.