[BOJ] 1759. 암호 만들기(Python) / DFS

www.acmicpc.net/problem/1759

1759번: 암호 만들기

DFS 알고리즘과 combination 모듈을 활용한 것 두 가지 방법으로 풀어보았다.

물론 조합(Combination)을 구한다는 본질은 같다.

 

 

파이썬 풀이는 다음과 같다.

 

• 방법 1 - dfs로 comb 함수 구현. 시간은 148ms 소요

---

import sys
input = sys.stdin.readline

def comb(depth, k, temp):
    if depth == L:
        vowel = 0
        for s in temp:
            if s in "aeiou":
                vowel += 1
        if vowel >= 1 and L-vowel >= 2:
            print(temp)
        return
    for i in range(k, C):
        comb(depth+1, i+1, temp + A[i])

# main
L, C = map(int, input().split())
A = sorted(list(input().split()))
comb(0, 0, "")

---

• 방법 2 - combination 모듈과 set 자료구조 사용. 코드가 훨씬 깔끔한 것 같다. 역시 모듈은 쓰라고 있는 것.

              시간은 124ms 소요

---

from itertools import combinations

L, C = map(int, input().split())
A = sorted(list(input().split()))
vowel = set("aeiou")
for comb in combinations(A, L):
    set_comb = set(comb)
    # 교집합 원소 1개 이상과 차집합 원소 2개 이상인 조건을 만족시키면 출력
    if set_comb & vowel and len(set_comb - vowel) >= 2:
        print(''.join(comb))

---

• 고찰 : 문제 풀 때 Set 자료구조를 잘 활용하면 코드가 훨씬 깔끔해질 수 있겠다ㅎㅎ