[백준] 1759. 암호 만들기 - python

오늘 푼 문제는 백준 1759 암호 만들기다. 

 

[백준] 1459. 암호 만들기

시도1 → 실패

아이디어

• 첫 시도는 단순하다. 조합으로 숫자를 뽑아서 출력하려고 했다.
• 그러나 조합이 너무 많았고 결과도 제대로 나오지 않았다.
• 코드도 복잡하고 for문을 너무 많이 돌았다. 나중에 해설 코드를 보고 이상하게 풀었음을 알았다…
• 코드는 다음과 같다.

from itertools import permutations, combinations
#서로 다른 L개의 알파벳, 문자의 종류는 C개 있다. 가능성 있는 암호는 총 몇개?
# import sys
# input = sys.stdin.readline
l,c = map(int, input().split())
candidate = list(input().split())
moeum = ['a','e', 'i', 'o', 'u']
vowels =[]
consonants = []
# 자모 분리
for alpha in candidate:
    if alpha in moeum:
        vowels.append(alpha)
    else:
        consonants.append(alpha)
# 뽑는 것은 순서 상관 없도록, 중복 허용X   -> combinations로 뽑는다.   
# vows 중 1개, cons 중 2개 
# 여기에 있는 것들은 빼고 나머지(c-3) 중에서 l-3개 뽑기
# 뽑은 총 l개를 증가하는 순서로 sort
vow = list(combinations(vowels,1))# 무조건 하나만 뽑는다.
cons = list(combinations(consonants,2))
answer=[]
for v in vow:
    for j in cons:
        password=[v[0], j[0], j[1]]
        #for문으로 이 3개가 포함되지 않은 값들을 찾고, 여기서 다시 l-3개를 뽑는다?
        temp=[]
        for k in candidate:
            if k != v[0] and k!=j[0] and k!=j[1]:
                temp.append(k)
        rest = list(combinations(temp,l-3))
        print(password)
        for r in rest:
            password=[v[0], j[0], j[1]]
            password.append(r[0])
            password.sort()
            if password not in answer:
                answer.append(password)
            # print(":",answer)
for a in answer:
    print(''.join(a))

시도2 → 성공

• 처음에 너무 복잡하게 생각했다.
• 먼저 for 문으로 숫자 L개로 모든 조합을 찾은 다음, 여기에 모음 최소 1개, 자음 2개가 포함되어 있는지만 확인하고 포함되어 있다면 출력하면 되었다.
• python으로 해결할 때에는 더 간결하게 풀어야겠다.

from itertools import combinations
# import sys
# input = sys.stdin.readline
l,c = map(int, input().split())
candidate = list(input().split())

vowels = ['a','e', 'i', 'o', 'u']
candidate.sort()

for password in combinations(candidate, l):
    cnt = 0
    for ch in password:
        if ch in vowels:
            cnt +=1
    if cnt >=1 and l-cnt >=2:
        print(''.join(password))

Backtracking

• 이때 combination 라이브러리를 사용하지 않고 dfs를 사용해서 combination을 만들 수 있다.
• 모든 index를 탐색하면서 이미 뽑았다면 다음 index로 옮기고, 아니라면 string에 추가해 조합을 구현할 수 있다.

import copy
# nCr
string=[]
result=[]
visited=[]
def combination(candidate, r, index):
    # r개를 뽑았다면 result에 넣고 탐색 끝
    if len(string) == r:
        result.append(copy.deepcopy(string))
        return
    #index 0부터 탐색한다. 이미 뽑았다면 다음 인덱스부터 뽑는다. 
    for i in range(index, len(candidate)):
        # 이미 뽑았다면
        if i in visited:
            continue
        string.append(candidate[i])
        visited.append(i)
        combination(candidate, r, i+1)
        string.pop()
        visited.pop()

 

이전에는 구름톤 챌린지를 달성했고 이번에는 코드 트리 챌린지를 달성해서 하반기 코딩테스트를 통과해야겠다.