[Python] 백준 1795번. 암호 만들기

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

1759번: 암호 만들기

문제: 주어진 문자를 가지고 L자리 비밀번호를 조합하여 비밀번호를 풀려고 한다.

주의 할 점은 비밀번호 조합에는 최소 하나의 모음과, 최소 두개의 자음을 포함하고 있어야 한다.

 

• 문자가 4개 만들어지면 반환하도록 한다.
• 입력받은 문자열은 정렬이 되어야 한다.
  • 출력결과를 보면 문자가 오름차순으로 정렬이 된 것으로 보인다.
  • 결국 첫번째 자리 < 두번째 자리 < 세번째 자리 < 네번째 자리순으로 정렬되어야 한다.
•  반복을 계속 하도록 한다. 'a' 는 고정 그 뒤 'c','i','s' 문자를 점차 늘려가며 4자리 숫자를 찾아가도록 한다.
  
  • 'c' -> 'i','s','t' 순으로 자리를 만들어 가려고 한다.
  • 문자가 정렬된순으로 만들어지기 때문에 's'가 처음으로 들어가게되면 세자리 비밀번호밖에 만들지 못한다.
• 나의 고민흔적

---

문자열을 입력받아 정렬을 해준다.

words = input().split()
words.sort()

 

정렬된 문자열을 세자리 a, c, i 값만 돌릴 수 있도록 길이는 C-L+1의 값을 준다.

• 만약 7자리 숫자로 4자리 비밀번호를 만든다고 한다면 [a,b,c,d,e,f,g] e가 처음으로 값이 들어가게 되면 e,f,g 로만 비밀번호를 만들기 때문에 4자리 비밀번호를 만들지 못한다. 7-4+1=4 즉 d까지만 값이 넘어가도록 하는 것

for i in range(C-L+1):
    find_password(i)

 

find_password(0) 으로 예시를 들어보자

• dfs(0, 'a') 로 dfs 함수를 호출하여 'a' 가 처음으로 오는 비밀번호 조합을 찾을 수 있도록 한다.
• 만약 글자가 4(L)이 된다면 가지치기를 하는 함수로 이동한다.
• 'a' 값 뒤에는 반드시 'a' 보다 큰 값이 와야 한다. 그것을 위한 조건문을 걸어둔다.

def find_password(idx):
    def dfs(idx, path):
        if len(path) == L:
            if check(path):
                print(path)
                return
        for i in range(idx, len(words)):
            if path[-1] < words[i]:
                dfs(i+1, path+words[i])

    dfs(idx, ""+words[idx])

 

4글자가 되었으면 이 문자가 최소 모음 1개 자음 2개로 구성되어있는지 확인이 필요하다. 그것을 위한 함수를 추가해준다.

def check(path):
    #모음길이  자음길이
    v_cnt, c_cnt = 0, 0
    vowel = ['a', 'e', 'i', 'o', 'u']
    # 최소 한개의 모음, 최소 두개의 자음
    for i in path:
        if i in vowel:
            v_cnt += 1
        else:
            c_cnt += 1
    if v_cnt >= 1 and c_cnt >= 2:
        return True
    else:
        return False

---