[class3]백준 1759번(암호 만들기) - 코테공부 24일차(2025.02.15)

문제유형

조합 알고리즘

풀이 방법 도출 과정

1. 조합을 물어보는 문제로 조합 알고리즘을 사용하면된다.

2. 하지만 모음 조합 1개, 자음 조합 2개를 사용해서 새로운 것을 만드는 것이기에 모음, 자음을 분리하는 것이 필요하다.

3. 또한  모음 자음을 분리했으면 이를 서로 조합해야한다.

4. 이를 토대로 코드를 작성해보도록 하겠다.

시간 복잡도

가장 최악을 구하자면 조합의 수는 O(15 choose 14)이고, 각 조합에 대해 O(14)만큼 처리하는 것이므로 O(15 choose 14 * 14)이다. 이것은 시간 복잡도가 시간에 비해 충분하다는 것을 보여준다.

코드 및 간단설명

combinations 함수를 사용하여 문제를 풀었다. 

from itertools import combinations

# 모음 리스트
vowels = ['a', 'e', 'i', 'o', 'u']

# 입력 받기
L, C = map(int, input().split())
chars = input().split()

# 문자들을 오름차순으로 정렬
chars.sort()

# 가능한 모든 조합을 찾기
for comb in combinations(chars, L):
    # 모음과 자음의 개수 계산
    num_vowels = sum(1 for c in comb if c in vowels)
    num_consonants = L - num_vowels  # L - 모음 수 = 자음 수
    
    # 조건을 만족하면 출력
    if num_vowels >= 1 and num_consonants >= 2:
        print(''.join(comb))

다른 풀이

1) 백트래킹(DFS) 사용

아래는 모든 조합을 생성한 후에 필터링하는 대신 백트래킹(DFS)을 이용하여 조건을 만족할 가능성이 없는 경로를 일찍 배제(pruning)하는 방법이다. 이 방식은 불필요한 조합 생성을 줄여주는 효과가 있어, 평균적인 실행 시간 측면에서 더 효율적일 수 있다.

# 모음 리스트
vowels = {'a', 'e', 'i', 'o', 'u'}

# 입력 받기
L, C = map(int, input().split())
chars = input().split()

# 문자들을 오름차순으로 정렬
chars.sort()

def dfs(start, chosen, vowels_count, consonants_count):
    # 길이가 L에 도달하면 조건 검사 후 출력
    if len(chosen) == L:
        if vowels_count >= 1 and consonants_count >= 2:
            print("".join(chosen))
        return
    
    # 남은 문자 수가 부족하면 더 이상 진행하지 않음 (백트래킹)
    if len(chosen) + (C - start) < L:
        return

    for i in range(start, C):
        char = chars[i]
        if char in vowels:
            dfs(i + 1, chosen + [char], vowels_count + 1, consonants_count)
        else:
            dfs(i + 1, chosen + [char], vowels_count, consonants_count + 1)

dfs(0, [], 0, 0)