[파이썬/Python] 백준 9012번 괄호

[파이썬/Python] 백준 9012번 괄호

9012번: 괄호

---

문제

괄호 문자열(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”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1 

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

예제 출력 1 

NO
NO
YES
NO
YES
NO

예제 입력 2 

3
((
))
())(()

예제 출력 2

NO
NO
NO

풀이 1

import sys
input = sys.stdin.readline

# T만큼 반복하여 테스트 데이터를 입력 받음
for _ in range(int(input().rstrip())):
    # 문자열 입력받음
    case = input().rstrip()  
    # 좌측 괄호와 우측 괄호를 카운트하기 위한 변수와, 잘못된 괄호 조합을 체크하기 위한 변수 초기화
    cnt_left, cnt_right, check = 0, 0, 0  
    # 입력받은 문자열의 각 문자를 하나씩 검사
    for i in case:  
        if i == '(':  # 좌측 괄호를 만나면 cnt_left를 1 증가
            cnt_left += 1
        # 우측 괄호를 만나면 cnt_right를 1 증가하고, 잘못된 괄호 조합이 있는지 체크
        else:
            cnt_right += 1
            # cnt_right가 cnt_left보다 크면 잘못된 괄호 조합이므로 check를 1로 변경
            if cnt_right > cnt_left:  
                check = 1
    # 입력받은 문자열에서 좌측 괄호와 우측 괄호의 수가 같으면
    if cnt_left == cnt_right:  
        if check: print('NO')  # 잘못된 괄호 조합이 있으면 NO 출력
        else: print('YES')  # 잘못된 괄호 조합이 없으면 YES 출력
    else: print('NO')  # 좌측 괄호와 우측 괄호의 수가 다르면 NO 출력

이 코드의 시간 복잡도는 입력받은 문자열의 길이가 N이라고 할 때 O(N)이다.

for문에서는 문자열의 길이 N만큼 반복하고, 반복문 내부에서는 상수시간이 걸리는 연산만 수행하므로, 전체적으로는 O(N)의 시간 복잡도를 가진다. 따라서 입력받은 문자열의 길이에 비례하는 시간이 소요된다.

 

풀이 2

import sys
vps = sys.stdin.readlines()[1:]  # 여러 줄의 문자열을 한번에 입력 받음

for v in vps:  # 입력 받은 문자열의 각 줄을 하나씩 검사
	v = v.rstrip()  # 문자열 끝에 있는 공백과 개행문자를 제거
	while '()' in v:  # 문자열에서 ()를 찾을 때까지 반복
		v = v.replace('()', '')  # ()를 제거
	if v:  # 문자열이 비어있지 않으면 NO 출력
		print('NO')
	else:  # 문자열이 비어있으면 YES 출력
		print('YES')

replace 메소드를 사용하여 코드를 훨씬 깔끔하게 작성할 수 있었다. 메소드의 존재 자체는 알고 있었지만 아이디어는 떠올리지 못했다.

파이썬에서는 문자열이 비어있지 않으면 True로 간주되는 것도 처음 알았다.

 

입력 부분이 너무 간단해서 더 놀라웠다. 테스트케이스의 수를 알 필요도 없었고, 입력을 반복해서 받을 필요가 없었다.

 

 

시간 복잡도 측면에서는 입력받은 문자열의 총 길이가 N이라고 할 때, while문에서 문자열의 길이가 최대 N이므로, while문 내부의 replace 연산이 최대 N번 수행될 수 있다. 하지만 replace 연산의 시간 복잡도는 상수시간이므로, 전체적으로는 O(N)의 시간 복잡도를 가진다. 따라서 입력받은 문자열의 길이에 비례하는 시간이 소요된다.

참고자료

로그인

 

python] 파이썬 텍스트파일 내용 불러오기, 텍스트 내용으로 리스트 만들기 - f.readlines, 리스트 슬