[자료구조] [BJ9012] 괄호

코드 플러스

🚩 문제 설명

BJ9012

⏱️ 시간 복잡도
▪️ 테스트 케이스의 갯수 T가 주어진다.
▪️ 각 테스트 케이스 마다 VPS 인지 아닌지 확인 해야한다.
▪️ 괄호 문자열의 길이는 2 이상 50 이하 이다.
▪️ 시간 복잡도는 O ( T x 50 ) 이라고 볼 수 있다.
▪️ O ( N x N ) 이라고 볼 수도 있다.

◾ 괄호 문자열이란 (Parenthesis String, PS)

• '(' 와 ')' 로 구성되어 있는 문자열을 뜻한다.
• 그 중에서 괄호의 모양이 바르게 구성된 문자열을 Valid PS로 VPS 라고 부른다.

◾ 주어지는 PS 들이 VPS인지 아닌지 구분하는 프로그램을 작성하는 문제.

 

 

 

---

 

 

 

✅ 입출력

return ➡️ PS가 VPS인지 아닌지 YES or No로 반환한다.

✔️ 예제 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

NO
NO
YES
NO
YES
NO

 

✔️ 예제 2

3
((
))
())(()

NO
NO
NO

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

N = int(input())
pss = [input() for _ in range(N)]

for ps in pss:
    flag = True
    check = 0
    for p in ps:
        if p == '(':
            check += 1
        else:
            check -= 1

        if check < 0:
            flag = False
            break

    if check == 0 and flag == True:
        print("YES")
    else:
        print("NO")

💬 Point

➡️  N : 테스트 케이스의 갯수
➡️  pss : PS 문장이 담겨있는 배열
➡️  check : VPS라면 check 가 0이 되어야 한다.
➡️  flag로 VPS인지 아닌지 확인한다.

◾ check를 이용하여 VPS인지 아닌지 판별한다.

• 만약 '(' 괄호가 나온다면 +1 을 한다.
• ')' 괄호가 나온다면 -1 을한다.
• VPS는 쌍을 이루기 때문에 check가 0이 되어야 한다.
• 만약 ()) 이런식이면 +-- 가 돼서 - 가 된다. 이러면 flag를 False로 만들고 break 한다.

◾ flag가 True이고 check가 0인 값들만 YES라고 출력한다.

 

 

 

 

 

 

 

 

 

 

 

---