[백준 1759] 암호 만들기 (Python)

👩🏻‍💻문제링크

[백준 1759] 암호 만들기 (Python)

✍️Idea Sketch

2021-07-29

1. 풀이법

• 방법 1. DFS 조합 구현
• 방법 2. itertools 라이브러리 사용

from itertools import combinations

words = combinations(alpha, L)  
# combinations(조합할 원소의 배열, 조합할 원소의 개수)

2. 서로 다른 L개의 알파벳을 뽑은 후(조합), 문제조건을 만족할 때 print

3. 놓친 부분 : 입력값을 받자마자 정렬하기

올바른 코드

L, C = map(int, input().split())
alpha = sorted(input().split())  #1, 입력값을 받자마자 정렬할 것

문제상황 : 아래와 같이 print할 때만 정렬하면, 기대값과 출력값의 순서가 달라짐

alpha = input().split()  #1

def is_password(arr):
  print(''.join(sorted(arr)))  #2

• 입력값

4 6
a t c i s w

• 기대값

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

• 출력값

acit
acst
actw
aist
aitw
astw
acis
aciw
acsw
aisw
cist
citw
istw  # 기대값과 다름
cisw  # 기대값과 다름

✍️소스코드

2021-07-29

조합을 구현한 풀이, 84ms 통과

L, C = map(int, input().split())
alpha = sorted(input().split())  #1

def is_password(arr):
  cnt_vow = 0
  for i in arr:
    if i == 'a' or i == 'e' or i == 'i' or i == 'o' or i == 'u':
      cnt_vow += 1
  if cnt_vow >= 1 and L - cnt_vow >= 2:
    print(''.join(arr))  #2

def dfs(v, arr):
  if len(arr) == L:
    is_password(arr)
    return
  if v == C:
    return
  arr.append(alpha[v])
  dfs(v+1, arr)
  arr.pop()
  dfs(v+1, arr)

dfs(0, [])

itertools을 사용한 풀이, 72ms 통과

from itertools import combinations

L, C = map(int,input().split())
alpha = sorted(input().split())
words = combinations(alpha, L)

for word in words:
    cnt_vow = 0
    for i in word:
        if i in "aeiou":
            cnt_vow += 1

    if cnt_vow >=1 and L - cnt_vow >=2:
        print(''.join(word))