반응형
📚 괄호 제거
문제
어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.
이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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
✍ 접근
- stack, combinations
정답코드
# ✨ 입력
import sys
from itertools import combinations
input = sys.stdin.readline
stack = []
arr = input().rstrip()
glst = []
resarr = set()
# ✨ 괄호 쌍 위치 구하기
for i in range(len(arr)):
if arr[i] == '(':
stack.append(i)
elif arr[i] == ')':
s = stack.pop()
glst.append((s,i))
# ✨ 조합을 이용해 괄호 제거하기
for i in range(1,len(glst)+1):
for comb in combinations(glst,i):
tmp = list(arr)
for x in comb:
tmp[x[0]] = ""
tmp[x[1]] = ""
resarr.add("".join(tmp))
for x in sorted(list(resarr)):
print(x)
해설
괄호 쌍 위치 구하기
- stack에 (의 위치를 넣고, )가 나왔을 때 (의 위치와 )의 위치를 함께 glst에 넣어준다
조합을 이용해 괄호 제거하기
- 1부터 괄호 쌍의 개수 +1까지 for문을 돌고
- 각 개수일 때 조합을 구해준다
- list를 받고
- 조합 내부 요소들을 돌면서 tmp를 비워준다.
- 중복되는 값이 있으니 set에 넣어주고, 다시 list로 변환해서 sort 후 출력해준다
⭐ 배움
- 문자열은 대부분 정해진 풀이 방식이 없으니 생각한 대로 풀어보자
반응형
'🏄♀️ 코딩테스트 > 🐍 Python' 카테고리의 다른 글
[ 백준 18428 해설 ] ( python ) 감시 피하기 (0) | 2022.07.16 |
---|---|
[ 백준 22942 해설 ] ( python ) 데이터 체커 (0) | 2022.07.16 |
[ 백준 2504 해설 ] ( python ) 괄호의 값 (0) | 2022.07.16 |
[ 백준 10610 해설 ] ( python ) 30 (0) | 2022.07.13 |
[ 백준 14889 해설 ] ( python ) 스타트와 링크 (1) | 2022.07.13 |