스택&큐(유형정리) - 백준 2800

2800번: 괄호 제거 (acmicpc.net)

2800번: 괄호 제거

 

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1 복사

(0/(0))

예제 출력 1 복사

(0/0)
0/(0)
0/0

예제 입력 2 복사

(2+(2*2)+2)

예제 출력 2 복사

(2+2*2+2)
2+(2*2)+2
2+2*2+2

예제 입력 3 복사

(1+(2*(3+4)))

예제 출력 3 복사

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

 

 

솔직히 골드랍시고 문제가 좀 어려웠다. 바로 직전에 괄호제거를 풀어보았음에도 불구하고 단순한 괄호의 제거가 아니라 전체적인 식을 출력해야 하기 때문에 조합, set, stack 등 다양한 방식으로 문제를 풀어야 했다.

 

※ 알고리즘

1. 식을 입력받는다.

2. stack 리스트, 최종값을 넘기기 전에 셋팅하는 temp 리스트, 최종결과값인 result 리스트가 필요하다.

3. result 리스트는 중복제거를 위해 set으로 만들어준다.

4. '(' 나오면 일단 stack에 담고, ')' 나오면 stack에서 pop 시켜서 temp 리스트에 잠시 담아둔다.

5. combinations를 이용해서 temp 리스트에서 가능할 수 있는 조합들을 찾는다.

6. 문자열을 다시 그대로 복사한다.(이 때, list(n)과 같이 list를 붙여주어야 한다.)

7. x,y가 조합에 있을 때, 공백을 담는다.

8. 조합값을 합쳐서 result 리스트에 담는다.

9. set은 sort() 사용이 불가능하므로 list로 변환시켜주고, sort()로 정렬시켜준다.

10. result를 반복문으로 모두 출력시킨다.

 

from itertools import combinations

n = list(input())

stack = []       #stack리스트
temp = []        #result로 넘기기 전에 담아두는 리스트
result = set()   #최종결과 - 중복제거를 위해 set으로

for i in range(len(n)):
    if n[i] == '(':               #'(" 나오면 stack에 담기
        stack.append(i)
    elif n[i] == ')':             #')' 나오면 stack에서 pop 시켜서 그대로 temp 리스트에 잠시 담아둠.
        temp.append((stack.pop(), i))

for i in range(1, len(temp) + 1):       #temp 리스트에서 가능한 조합들을 찾기
    comb = list(combinations(temp, i))

    for j in comb:                      #문자열을 다시 그대로 복사
        copy_str = list(n)
        for x,y in j:
            copy_str[x] = ''            #x,y가 조합에 있을 때, 공백 넣기
            copy_str[y] = ''

        result.add(''.join(copy_str))     #조합값을 합쳐서 result 리스트에 담기

result = list(result)                 #다시 list로 바꾸어주고 sorting 정렬
result.sort()

for i in result:
    print(i)

 

주석을 달아가면서 천천히 문제를 풀어보았다. 꽤나 복잡했고 이전 브루트포스에서 많이 사용하던 combinations와 set을 떠올리는 과정이 이 문제의 가장 핵심이 아닐까? 생각이 든다.