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

백트래킹, 골드 1

🔐

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

내 풀이

def dfs(n, s, lst):
    if n == L: # 길이가 L인 암호가 만들어진 경우
        ans.append(lst) # 정답 리스트에 추가
        return
    else:
        for i in range(s, C):
            dfs(n+1, i+1, lst+[chars[i]]) # 암호에 알파벳 추가

vowel = ['a', 'e', 'i', 'o', 'u'] # 모음 리스트
chars = [] # 주어지는 문자들
ans = [] # 정답 리스트

L, C = map(int, input().split())
chars = sorted(list(input().split())) # 정렬

dfs(0, 0, [])

for i in range(len(ans)):
    vowel_count = 0
    consonant_count = 0

    for j in ans[i]:
        if j in vowel: # 모음의 개수 체크
            vowel_count += 1
        else: # 자음의 개수 체크
            consonant_count += 1
    if vowel_count < 1 or consonant_count < 2: # 모음이 1개 미만이거나, 자음이 2개 미만인 경우
        ans[i] = "" # 임의로 삭제
    
for i in ans:
    if i != '': # 빈 문자가 아닌 경우 정답
        print(*i, sep='')

 

직관적이지만 다소 난잡하게 풀었다.

 

✔️ 우선 암호가 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야 한다는 조건을 생각하지 않고,

L개의 알파벳으로 구성할 수 있는 모든 암호를 구해서 ans(정답 배열)에 추가했다.

✔️ ans(정답 배열)를 돌면서 조건을 위배하는 리스트를 임의 삭제 처리(빈 문자열로 치환)했다.

✔️ 빈 문자열이 아닌 경우, 조건을 만족하는 암호이기 때문에 출력한다.

 

 

다른 풀이

def dfs(n, vowel_count, str):
    if n == C: # 모든 알파벳의 사용여부 선택 완료
        if len(str) == L and vowel_count >= 1 and L - vowel_count >= 2:
            ans.append(str)
        return
    
    # 포함하는 경우
    dfs(n+1, vowel_count + table[ord(chars[n])], str+chars[n])
    # 포함하지 않는 경우
    dfs(n+1, vowel_count, str)

L, C = map(int, input().split())
chars = sorted(input().split()) # 정렬

# lookup table (모음인 경우 1, 자음인 경우 0)
table = [0] * 128
for i in "aeiou":
    table[ord(i)] = 1

ans = []

dfs(0, 0, "") # index, 모음의 개수, 완성된 암호 문자열

for i in ans:
    print(i)

 

✔️ dfs를 모든 알파벳의 사용여부가 선택될 때까지( n == C ) 반복한다.

↪ 조건을 검사한 뒤, 올바른 암호인 경우에만 ans(정답 배열)에 추가한다.

✔️ 알파벳을 암호에 포함하는 경우와 포함하지 않는 경우로 나누어서 dfs를 각각 호출한다.

✔️ 모음과 자음을 구분하기 위해 lookup table을 사용한다.

↪ 생소했던 부분이다.

 

LookUp Table (룩업 테이블) : 주어진 연산에 대해 미리 계산된 결과들의 집합(배열), 결과값을 가진 배열

ord() : 하나의 문자를 인자로 받아 해당 문자의 유니코드 정수 반환

ex) ord('a') → 97

 

쪼금 더 빠르다

 

참고한 풀이 영상

 

https://www.youtube.com/watch?v=3WS6LMgnYzA&list=PLodgw23vNd_UFQeV8GQtVHrT38VWE6iJv&index=16