[백준 02800] 괄호 제거 [Python]

문제

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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개이다. 

출력

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

2800번: 괄호 제거

---

풀이

입력으로 주어지는 수식( f )가 올바르지 않은 경우는 없다.

올바르게 주어지는 f에 대해 괄호쌍을 제거하여 얻을 수 있는 서로 다른 식을 사전 순으로 출력하는 문제다.

괄호의 위치에 대한 조합 문제로 풀이했다.

 

스택에 값을 직접적으로 저장하며 해결하는 문제가 아닌, 값의 정보를 저장하며 푸는 문제다. 

 

우선 괄호쌍의 위치를 얻기위해 stack에 '('의 인덱스를 담고, ')'가 나오면 다시 빼주어 하나의 쌍으로 위치를 저장하자.

이제 pair에 저장된 괄호 쌍의 위치들을 조합을 통해 모든 경우의 수를 뽑아주고.

이에 대해 문자열을 생성해 중복 없이 저장해주자.

문제에서는 서로 다른 식을 정렬해 출력하라는 조건이 주어졌으니 정렬 후 출력하면 된다.

---

소스코드

보기

---

출처

https://www.acmicpc.net/problem/2800