프로그래머스_python_올바른 괄호의 갯수

문제

https://programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

풀이

1. 접근하기

괄호쌍 2개를 이용한다고 할때, 아래와 같다.

• 탐색하기

문자열 뒤에 "("을 붙인다.

올바른 괄호쌍이라면, 탐색을 계속한다.

 

문자열 뒤에 ")"을 붙인다.

올바른 괄호쌍이라면, 탐색을 계속한다.

 

• 올바른 괄호쌍

")"의 개수가 "("보다 많지 않다.

2. 시간초과

• '('의 개수 기록하기

# "("의 개수를 기록하지 않음
def solution(n):
    answer = 0
    stack = [(1, 1)]
    while stack : 
        size, check = stack.pop()
        if size==2*n :
            if check==0 : answer += 1
            continue
        
        # add "("
        if 0<=check+1<=n : 
            stack.append((size+1, check+1))
            
        # add ")"
        if 0<=check-1<=n : 
            stack.append((size+1, check-1))

    return answer
    
    # "("의 개수를 기록함
    # "("의 개수가 순서쌍의 개수n보다 커지지 않도록 체크
    def solution(n):
    answer = 0
    stack = [(1, 1, 1)]
    while stack : 
        size, check, count = stack.pop()
        if size==2*n :
            if check==0 : answer += 1
            continue
        
        # add "("
        if 0<=check+1<=n and count+1<=n: 
            stack.append((size+1, check+1, count+1)) 
            
        # add ")"
        if 0<=check-1<=n and count<=n: 
            stack.append((size+1, check-1, count))

    return answer

"("의 개수를 저장하기 전에는 마지막 케이스에서 시간초과 오류가 있었지만, "("가 괄호쌍의 개수보다 많은 경우를 탐색에서 제외하였더니 모든 케이스에서 통과할 수 있었다.

• 문자열 사용하지 않고 표현하기

# 문자열을 이용한 풀이
def solution(n):
    answer = 0
    stack = [('(', 1, 1)]
    while stack : 
        token, check, count = stack.pop()
        if len(token)==2*n :
            if check==0 : answer += 1
            continue
        
        if 0<=check+1<=n and count+1<=n: 
            stack.append((token+'(', check+1, count+1))
        if 0<=check-1<=n and count<=n: 
            stack.append((token+')', check-1, count))
            
    return answer

괄호쌍의 개수가 1 ≤ n ≤ 14로 문자열의 크기가 크지 않아서, 실행시간이 크게 줄어들지는 않았다.

3. 다른 풀이

• 카탈란(카탈랑) 수

문자열을 첫 괄호, 나머지 괄호로 나눈다.

첫번째 괄호를 기준으로 내부 괄호의 수와 외부 괄호의 수를 곱한다.

3쌍의 괄호라면, 아래가 표가 성립한다.

내부 괄호의 수	외부 괄호의 수	예시
2	0	((())) , (()())
1	1	(())()
0	2	()(()), ()()()

https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

카탈랑 수 - 위키백과, 우리 모두의 백과사전

코드

def solution(n):
    answer = 0
    stack = [(1, 1, 1)] # 문자열의 len, "("개수-")"개수, "("의 개수
    while stack : 
        size, check, count = stack.pop()
        if size==2*n :
            if check==0 : answer += 1
            continue
        
        # add "("
        if 0<=check+1<=n and count+1<=n: 
            stack.append((size+1, check+1, count+1))
            
        # add ")"
        if 0<=check-1<=n and count<=n: 
            stack.append((size+1, check-1, count))

    return answer