💡문제 분석 요약

주어진 문자열이 완전한 괄호 형태인지 판별하고 알맞은 출력값을 내야 한다.

완전한 괄호 형태면 “YES”, 그렇지 않으면 “NO”를 출력하기

💡알고리즘 설계

1. 주어지는 테스트 케이스 개수(N)만큼 반복문이 실행된다.
2. 빈 리스트 stack을 N번 초기화시키고, 문자열(vps)를 받아온다.
3. 문자열을 순회하며 해당 문자가 “(”이면 stack에 append, “)”이면 stack이 비어있지 않으면 pop, 비어있다면 완전한 괄호 형태가 아니기 때문에 “NO”를 출력하고 반복문을 빠져나가며 다음 테스트 케이스를 탐색한다.
4. 반복문이 실행되는동안 stack이 비어있지 않아 반복문이 종료가 된다면 stack에 남아있는 “(”가 있는 지 확인한다.

4-1) stack 안에 “(”이 남아있다면 “NO” 출력

4-2) stack이 비어있다면 “YES” 출력

💡코드

import sys
N = int(sys.stdin.readline())

for _ in range(N):
    stack = []
    vps = sys.stdin.readline().strip()
    for i in vps:
        if i == "(":
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                print("NO")
                break
    else:
        if stack:
            print("NO")
        else:
            print("YES")

💡시간복잡도

테스트 케이스의 개수를 N, 주어진 테스트 케이스 문자열의 최대 길이를 L이라 치면,

시간복잡도는 O(N*L) 이다.

💡 틀린 이유

알고리즘 설계의 4번 부분은 배제하고 풀어 옳지 않은 답을 출력함.

💡 틀린 부분 수정 or 다른 풀이

하나의 테스트 케이스에 대한 반복문이 종료됐다면 stack이 비어져 있는 지 여부를 한 번 더 고려해 봐야함을 깨닫고 알고리즘 설계에 4번 부분을 추가해 통과할 수 있었다.