[Algorithm] [Python] BOJ/백준 - 9012_괄호

괄호

INDEX

1. 문제 설명

• 입력
• 출력
• 에제 입출력

2. 제출코드

3. 코드설명

4. 다른 사람의 풀이

문제

---

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

---

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

---

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입출력

---

6

(())()) -> NO

(((()())() -> No

(()())((())) -> YES

((()()(()))(((())))() -> NO

()()()()(()()())() -> YES

(()((())()( -> NO

제출코드

---

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. '(' 가 ')'보다 먼저 나와야한다.

우선 test case 수를 입력받은 이후 해당 값만큼 반복을 진행한다.

각 순회차 마다 stack 을 새로 생성하고 sum 이라는 변수를 선언한다.

이후 입력받은 괄호를 stack 에 리스트 자료형으로 입력한다.

stack 각각의 원소를 순회하면서 같은 분기 타이밍에서 만일 원소가 ')' 일 경우 -1 , '(' 일 경우 +1 을 진행하여 짝을 확인한다.

다음 분기에서 sum 의 값이 음수인지 확인하여 예외처리를 진행한다.

리스트의 원소중 맨앞의 원소부터 순회를 진행하기 때문에 sum의 값이 음수가 나온다면 이는 잘못된 괄호라는 것을 입증할 수 있다.

반복문이 종료되면 sum 의 값을 기준으로 "YES" 또는 "NO를 출력한다.

다른 사람의 풀이

---

num = int(input())

for i in range(num):
    vps = list(input())
    while len(vps) != 0:
        if vps[0] == ')':
            print('NO')
            break
        else:
            if ')' in vps:
                vps.remove(')')
                vps.remove('(')
            else:
                print("NO")
                break
    if len(vps)==0:
        print("YES")

출처

이분은 입력받은 배열의 첫원소가 닫힌 괄호 ')' 인지 검증한 이후 배열 내에 ) 가 있다면 괄호 쌍 ')' , '(' 을 remove 하였다.

문제를 푸는 방식은 동일하였지만 코드의 가독성과 직관성이 좋았다.