백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2800 괄호 제거 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/2800

반응형

솔루션 살펴보기!!

import sys

def input():
    return sys.stdin.readline().rstrip()

s = input()
n = len(s)

# 괄호 쌍 인덱스를 기록할 리스트와 스택 초기화
bracket_index = [-1] * n
stack = []
pair_count = 0

# 괄호 쌍에 번호를 기록
for i, char in enumerate(s):
    if char == '(':
        stack.append(pair_count)
        bracket_index[i] = pair_count
        pair_count += 1
    elif char == ')':
        bracket_index[i] = stack.pop()

# 중복을 방지하기 위해 set을 사용하여 모든 가능한 결과 저장
results = set()
# 각 괄호 쌍을 선택할지 여부를 기록하는 배열
selected_pairs = [0] * pair_count

def generate_combinations(index):
    if index == pair_count:
        # 선택된 괄호쌍이 하나도 없는 경우는 처리하지 않음
        if any(selected_pairs):
            # 선택된 괄호쌍에 맞춰 문자열 생성
            filtered_string = ''.join(
                char for i, char in enumerate(s) 
                if bracket_index[i] == -1 or selected_pairs[bracket_index[i]] == 0
            )
            results.add(filtered_string)
        return

    # 현재 괄호쌍을 제거하는 경우
    selected_pairs[index] = 1
    generate_combinations(index + 1)

    # 현재 괄호쌍을 제거하지 않는 경우
    selected_pairs[index] = 0
    generate_combinations(index + 1)

# 재귀 호출 시작
generate_combinations(0)

# 사전순 정렬 후 출력
print('\n'.join(sorted(results)))

코드 흐름 설명 및 풀이 전략

이 코드는 주어진 문자열에서 괄호쌍을 제거하는 모든 가능한 경우의 수를 생성하여 출력하는 문제를 해결합니다. 단, 문자열에서 제거된 괄호쌍을 제외한 부분은 그대로 유지되어야 하며, 중복된 문자열은 제외하고 사전순으로 정렬하여 출력해야 합니다.

풀이 전략

1. 괄호쌍 번호 기록:
   • 주어진 문자열에서 괄호쌍에 번호를 붙여 각 괄호쌍이 서로 어떤 괄호쌍과 대응하는지를 기록합니다. 이는 괄호쌍을 제거할 때 대응되는 괄호를 동시에 제거할 수 있도록 하기 위함입니다.
2. 모든 괄호쌍 제거 경우의 수 생성:
   • 각 괄호쌍을 선택하거나 선택하지 않는 경우의 수를 재귀적으로 탐색합니다. 즉, 각 괄호쌍을 제거할지 말지를 선택하는 모든 조합을 만들어냅니다.
3. 중복 제거:
   • 중복된 결과를 방지하기 위해 set 자료구조를 사용하여 문자열을 저장합니다. 이를 통해 중복된 결과가 자동으로 제거됩니다.
4. 결과 출력:
   • 가능한 모든 경우의 문자열을 set에 저장한 후, 이를 사전순으로 정렬하여 출력합니다.

 

코드의 주요 개념과 흐름

1. 괄호쌍 번호 기록 (Preprocessing)

bracket_index = [-1] * n
stack = []
pair_count = 0

for i, char in enumerate(s):
    if char == '(':
        stack.append(pair_count)
        bracket_index[i] = pair_count
        pair_count += 1
    elif char == ')':
        bracket_index[i] = stack.pop()

 

• bracket_index 리스트는 문자열에서 괄호쌍의 번호를 기록하는 역할을 합니다.
• 열린 괄호 (가 나오면 스택에 현재 괄호쌍의 번호를 저장하고, 닫힌 괄호 )가 나오면 스택에서 해당 번호를 꺼내 대응되는 괄호쌍을 기록합니다.
• pair_count는 몇 번째 괄호쌍인지를 나타냅니다.

2. 재귀적으로 가능한 모든 경우의 수 탐색

def generate_combinations(index):
    if index == pair_count:
        if any(selected_pairs):
            filtered_string = ''.join(
                char for i, char in enumerate(s) 
                if bracket_index[i] == -1 or selected_pairs[bracket_index[i]] == 0
            )
            results.add(filtered_string)
        return

 

 

• generate_combinations 함수는 각 괄호쌍을 선택하거나 선택하지 않는 모든 경우의 수를 생성하는 재귀 함수입니다.
• index == pair_count인 경우, 모든 괄호쌍에 대해 선택 여부가 결정된 상태입니다. 그때까지의 선택 결과를 기반으로 새로운 문자열을 생성합니다.
• 선택된 괄호쌍이 하나도 없는 경우(any(selected_pairs)가 False일 때)는 처리하지 않음으로써 빈 문자열이나 괄호가 전부 남아있는 경우를 걸러냅니다.

3. 괄호쌍을 제거한 문자열 생성

filtered_string = ''.join(
    char for i, char in enumerate(s) 
    if bracket_index[i] == -1 or selected_pairs[bracket_index[i]] == 0
)

 

 

• 문자열을 생성할 때는, bracket_index[i] == -1인 문자는 괄호가 아닌 문자이므로 그대로 포함시킵니다.
• 선택된 괄호쌍(selected_pairs[bracket_index[i]] == 1)이 있는 경우에는 그 괄호쌍을 제거하고, 선택되지 않은 괄호는 그대로 유지합니다.

4. 중복 제거 및 출력

results = set()
generate_combinations(0)
print('\n'.join(sorted(results)))

 

 

• set 자료구조는 중복된 결과를 자동으로 제거합니다.
• 모든 가능한 경우의 수를 생성한 후, 이를 사전순으로 정렬하여 출력합니다.

728x90

주요 개념

1. 스택을 이용한 괄호쌍 처리:
   • 스택을 사용하여 열린 괄호와 닫힌 괄호의 쌍을 찾는 것은 괄호 문제에서 흔히 사용되는 기법입니다. 열린 괄호가 나올 때마다 스택에 해당 괄호의 인덱스를 저장하고, 닫힌 괄호가 나오면 스택에서 꺼내서 대응하는 열린 괄호의 인덱스를 찾습니다.
2. 재귀적 백트래킹 (Backtracking):
   • 이 문제에서는 재귀를 통해 각 괄호쌍을 포함할지, 제거할지를 결정하는 모든 조합을 생성합니다. 이는 일종의 백트래킹 기법으로, 모든 가능한 조합을 탐색하는 방법입니다.
3. 중복 제거를 위한 Set 사용:
   • 중복된 결과를 방지하기 위해 set을 사용합니다. 이를 통해 결과를 저장하는 과정에서 자동으로 중복이 제거되며, 성능적으로 효율적입니다.
4. 사전순 정렬:
   • 가능한 문자열을 출력할 때 사전순으로 정렬하라는 요구사항을 처리하기 위해 sorted() 함수를 사용하여 결과를 정렬합니다.

성능 고려사항

• 이 코드는 각 괄호쌍에 대해 선택할지 여부를 결정하는 모든 경우의 수를 처리하므로, 시간 복잡도는 O(2k)입니다. 여기서 k는 괄호쌍의 개수입니다. 각 경우에 대해 문자열을 생성하고, 결과를 set에 저장하는 과정이 추가됩니다.
• 따라서 괄호쌍의 개수가 많아지면 재귀 호출 횟수와 문자열 생성 횟수가 많아져 성능에 영향을 줄 수 있습니다. 그러나 문제의 크기가 적당하다면 충분히 효율적입니다.