[백준] 2800 - 괄호제거 (Python, combinations)

BAEKJOON Logo

이번엔 백준 2800 괄호 제거 문제를 풀어보겠습니다. 주요 자료구조는 스택을 사용하며, 조합(combinations)을 이용해 풀어보겠습니다.

2800번: 괄호 제거

Contents

---

*전체 코드

from itertools import combinations
problem = list(input()) # 문제 입력받는 리스트
p, brk_idx = [],[] # 괄호쌍 찾을 스택 -> p , 괄호쌍 인덱스 저장 이중리스트 -> brk_idx
result=set() # 결과 저장할 집합
for i,v in enumerate(problem): ## 괄호쌍 인덱스 저장 및 problem에서 괄호 제거
    if v == '(':
        problem[i]=''
        p.append(i)
    if v == ')':
        problem[i]=''
        brk_idx.append([p.pop(),i])      
for i in range(len(brk_idx)): ## 괄호쌍의 조합(combinations)을 이용해 괄호 추가
    for j in combinations(brk_idx,i):
        P=problem[:] ## problem리스트 복사
        for s,e in j:
            P[s]='(';P[e]=')' ## 괄호쌍 채우기
        result.add(''.join(P))
print(*sorted(result),sep='\n') ## 결과 출력

 

 

문제정의

문제 입력과 출력

입력으로 괄호 쌍이 올바르게 맞는 수식이 주어집니다. (괄호 쌍은 적어도 1개, 많아야 10개) 해당 수식에서 올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력해야 합니다. (괄호 쌍이 적어도 1개 이상이기 때문에, 제거되는 괄호 쌍은 1개 이상, 10개 이하)

 

 

import combinations 및 입력부

from itertools import combinations

problem = list(input()) # 문제 입력받는 리스트
p, brk_idx = [],[] # 괄호쌍 찾을 스택 -> p , 괄호쌍 인덱스 저장할 이중리스트 -> brk_idx
result=set() # 결과 저장할 집합

itertools의 combinations를 임포트 해줍니다. 괄호 쌍 조합들을 삽입할 때 쓰입니다. problem에 입력받는 수식을 쪼개 리스트로 저장합니다. p는 스택으로, 괄호 쌍을 찾을 때 사용합니다. brk_idx는 괄호 쌍의 인덱스를 저장할 이중 리스트로 쓰입니다. 결과에 중복을 제거하기 위해 집합(set)을 이용합니다. 예제 입력 1에 대해 problem의 출력은 아래와 같습니다.

* 출력

예제 입력 1에 대한 입력 리스트

 

combinations 간단 설명

combinations(p, r) 일 때, p에 대해 r개수만큼의 조합을 튜플로 출력합니다. 정렬된 순서이며, 반복되는 요소는 없습니다. 아래 예시에선 'ABCD'에서 2개의 조합을 쭉 출력하는 것입니다.

combinations('ABCD', 2)

AB AC AD BC BD CD

* 출력

combinations 결과 출력

 

핵심 알고리즘

괄호 쌍 인덱스 저장 및 괄호 제거 리스트 생성

for i,v in enumerate(problem): ## 괄호쌍 인덱스 저장 및 problem에서 괄호 제거
    if v == '(':
        problem[i]=''
        p.append(i)
    if v == ')':
        problem[i]=''
        brk_idx.append([p.pop(),i])

problem리스트를 enumerate를 사용하여, 인덱스(i)와 값(v)을 동시에 차례대로 반복해줍니다. 괄호 시작 부분 '('을 만나면, 스택(p)에 인덱스를 append 하고, 괄호 닫히는 부분 ')'을 만나면 스택(p)에서 pop 한 괄호 시작 부분의 인덱스와 괄호 닫히는 부분의 인덱스를 차례로 리스트로 만들어 brk_idx에 저장합니다. problem에서 괄호 부분은 모두 빈 문자열로 대치해줍니다. (나중에 괄호 쌍을 넣기 위한 용도)

백준의 예제 입력 1번에 대해 위 코드 결과 problem과 brk_idx는 아래와 같습니다.

* 출력

괄호 제거된 problem과 brk_idx

 

괄호 쌍의 조합(combinations)을 이용해 괄호 추가

for i in range(len(brk_idx)): ## 괄호쌍의 조합(combinations)을 이용해 괄호 추가
    for j in combinations(brk_idx,i):
        P=problem[:] ## problem리스트 복사
        for s,e in j:
            P[s]='(';P[e]=')' ## 괄호쌍 채우기
        result.add(''.join(P))

1. 괄호쌍 인덱스 리스트(brk_idx)에 대해 combinations를 이용 → 추가할 괄호 쌍의 인덱스를 사용합니다.

problem을 재사용하기 위해,

1. 즉, combinations의 2번째 인자로 0을 넣으면, 추가할 게 없는 경우(모든 괄호가 제외된 경우)가 됩니다.
   -> 0/0
2. 1을 넣으면 1개의 괄호 쌍을 제외한 경우가 됩니다. 
   -> (0/0), 0/(0)
3. 주어진 예시에서 괄호 쌍이 총 2개이므로, 이건 돌지 않습니다.

 

print(*sorted(result),sep='\n') ## 결과 출력

괄호 쌍이 제외된 게 중복일 수 있으니, 이를 모두 집합에 추가한 뒤 → sorted(사전 순 정렬) 하여 출력합니다.

* 출력

결과 출력