[백준 1759 암호 만들기] 문제 해설

[백준 1759 암호 만들기] 문제 해설

문제

Start

• 본 문제는 백트래킹 문제입니다. 백트래킹에 대해 자세히 알지 못한다면 백트래킹(Backtracking)이란? 글을 참고해주세요.

Step By Step

Step 1 입력

L, C = map(int, input().split())
inputList = list(map(str, input().split()))
inputList.sort()

• 문제에서 주는 값을 입력 받습니다.
• 알파벳 순으로 출력하기 위해서 .sort 함수를 이용해서 정렬합니다.

Step 2 암호문 조합 (solution 함수 후반부)

    def solution(L, inputList, combStr, index):

    (중략)

        solution(L, inputList, combStr+list(inputList[index]), index + 1)
        solution(L, inputList, combStr, index + 1)

• 재귀를 이용해서 지금의 암호문(combStr)의 뒤에 단어를 추가하거나 solution( ..., combStr+list(inputList[index]), ...)
• 재귀를 이용해서 지금의 암호문(combStr)의 뒤에 단어를 추가하지 않습니다. solution( ..., combStr, ...)
• 두 줄의 Code를 이용해서 inputList에 담긴 단어들을 이용해서 만들 수 있는 모든 경우의 수의 암호문 을 만들 수 있습니다.
• index를 1씩 증가시킴으로써 탐색이 inputList의 길이 보다 길어지지 않도록 할 것입니다.

Step 2 암호문 조합 (solution 함수 전반부)

# L: 입력 값 L(만들고자 하는 암호문의 길이)
# inputList : 입력 받은 알파벳을 넣은 리스트(조합할 수 있는 알파벳 종류) 
# combStr : 현재 암호문
# index : 몇 번째 Depth인지!
def solution(L, inputList, combStr, index):

[1]    if len(combStr) is L:
[2]        if check(combStr) is True:
[3]            print(''.join(combStr))
[4]        return;

[5]    if index >= len(inputList): # 안 쓰면 out of range!
[6]        return;

• [1] 줄: 길이 L의 암호를 만들어야합니다. 따라서 암호문 길이 L이 되면 해당 문자열(combStr) 뒤에 다른 문자가 오면 안됩니다.
• [2] 줄: check함수를 통해서 combStr이 문제의 조건에 맞는 암호문이 될 수 있는지 검사 합니다. 조건에 맞는 문자열이라면 True를 반환하고 [3] 줄에서 출력 할 것입니다.
• [5] 줄: 재귀 함수를 이용해서 inputList에서 단어를 선택하거나 선택하지 않음으로써 암호문들 만들었습니다. 무한히 재귀가 깊어질 수는 없고 inputList 길이 보다 깊어질 수 없습니다.

Step 3 암호문 검사

def check(combStr):
       vowel = 0
       consonant = 0

[1]    for char in combStr:
[2]        if char in ['a', 'e', 'i', 'o', 'u']:
               vowel += 1
[3]        else:
               consonant += 1

[4]     if consonant >= 2 and vowel >= 1:
            return True
[5]     else:
            return False

• [1] 줄: 암호문이 유요한지 반복문을 돌며 검사할 것입니다.
• [2] 줄: 모음이라면 vowel 값을 1 증가시킵니다.
• [3] 줄: 자음이라면 consonant 값을 1 증가시킵니다.
• [4] 줄: combStr이 자음 2개 이상 모음 1개 이상이면 참을 리턴합니다.
• [5] 줄: 자음 2개 이상 모음 1개 이상이 아니면 거짓을 리턴합니다.

[파이썬] 전체 코드

def check(combStr):
    vowel = 0
    consonant = 0

    for char in combStr:
        if char in ['a', 'e', 'i', 'o', 'u']:
            vowel += 1
        else:
            consonant += 1

    if consonant >= 2 and vowel >= 1:
        return True
    else:
        return False


def solution(L, inputList, combStr, index):

    if len(combStr) is L:
        if check(combStr) is True:
            print(''.join(combStr))
        return;

    if index >= len(inputList): 
        return;

    solution(L, inputList, combStr+list(inputList[index]), index + 1)
    solution(L, inputList, combStr, index + 1)


answer = 0
L, C = map(int, input().split())
inputList = list(map(str, input().split()))
inputList.sort()

combStr = []
index = 0

solution(L, inputList, combStr, index)