[백준] 암호 만들기

문제

백준 암호 만들기 https://www.acmicpc.net/problem/1759

 

코드

l, c = map(int, input().split())    # 암호길이, 후보 문자 개수
letters = sorted(list(map(str, input().split())))   # 후보 문자
arr = []


# 모음 세는 함수
def count_vowel(lst):
    return lst.count('a') + lst.count('e') + lst.count('i') + lst.count('o') + lst.count('u')


def recur(idx):
    if len(arr) == l:
    	# 모음 한개이상, 자음 두개 이상이면
        if count_vowel(arr) >= 1 and l - count_vowel(arr) >= 2:	
            print("".join(arr))
            return

    for i in range(idx, c):
        arr.append(letters[i])
        recur(i + 1)
        arr.pop()

recur(0)

 

풀이

l, c = map(int, input().split())    # 암호길이, 후보 문자 개수
letters = sorted(list(map(str, input().split())))   # 후보 문자
arr = []

입력 조건에 맞춰서 입력 l, c, letters를 입력받는다.

완성된 암호는 오름차순으로 정렬되어야 하기 때문에, letters를 미리 오름차순 정렬한다.

arr은 백트래킹시 정답을 담을 배열이다.

 

# 모음 세는 함수
def count_vowel(lst):
    return lst.count('a') + lst.count('e') + lst.count('i') + lst.count('o') + lst.count('u')

모음을 세는 함수를 선언한다.

매개변수로 받는 배열에 a, e, i ,o, u가 총 몇개 있는지 반환한다.

 

def recur(idx):

    if len(arr) == l:
    	# 모음 한개이상, 자음 두개 이상이면
        if count_vowel(arr) >= 1 and l - count_vowel(arr) >= 2:	
            print("".join(arr))
            return

    for i in range(idx, c):
        arr.append(letters[i])
        recur(i + 1)
        arr.pop()

arr에 후보글자들을 하나씩 추가한다. 

조건에 맞춰서 글자를 하나씩 추가하다가 종료조건에 만족하면 arr에 있는 숫자들을 출력하고 return 한다.

 

종료조건은

arr의 길이가 암호의 길이와 같고,

arr안에 모음이 한개 이상, 자음이 두개 이상 이어야한다.

 

새롭게 배운점/느낀점

• 골드 문제 인것에 약간 겁먹었지만, 백트래킹 개념을 탄탄히 다져놓았다면 쉽게 풀 수 있는 문제인것 같다.

 

더 나은 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)