1759. 암호 만들기 - 파이썬. 백트래킹, DFS

1759. 암호 만들기 

 

사용한 알고리즘 및 자료구조

1. DFS(백트래킹)
2. 집합

접근 방식

문제의 조건은 아래와 같다.

1. 중복되지 않는 알파벳들을 네 개 선택해서 나열해야 한다.
2. 암호는 오름차순으로 정렬되어야 하며
3. 자음이 2개, 모음이 1개 이상이여야 한다.

아래의 로직대로 풀었다. 

1. 입력 / 선언
   1. input을 받는다.
   2. 길이가 127인 아스키-리스트를 만든다. input값에 등장한 알파벳들을 아스키값으로 변환, askii 리스트의 해당 인덱스에 '값이 있음' 표시 해준다.
   3. 연산 DFS 연산한다. index가 97일 때부터 연산한다 (ord('a') == 97)
2. 연산
   1. 종료 조건 길이가 L일 때.
   2. 정답 조건 모음이 1개 이상, 자음이 2개 이상
   3. DFS연산 모든 아스키값을 순회하면서 특정 아스키 값이 '있을 떄' 사용한 것으로 체크한 후 (알파벳의 askii 값을 index로 하는 리스트의 값을 0으로) 재귀 호출.

문제 특이사항

자음, 모음, 길이, 오름차순 등의 조건들이 많다. 세심하게 구현하지 않으면 디버깅이 몹시 까다로울 것 같다.

 

어려웠던 점

문제가 번잡한 감이 있었다. 코드에 꼭 필요한 내용만 남기고 짧게 줄여보자.

 

느낀 점

askii --> char 형변환을 하지 않는 다른 사람의 코드가 훨신 더 빨랐다.

입/출력값의 크기와 성질을 잘 파악한 후 계산해야겠다.

 

풀었을 당시의 백준 티어

골드 5, 21-09-16

 

# 3. 연산
# a의 askii값은 97이므로 97부터 순회
def back_track(idx=97, length=0):

    # 3-1. 종료조건:
    # length (암호의 길이)가 L일때
    if length == L:
        # 3-2 정답 출력 조건
        # 모음이 1개 이상, 자음이 2개 이상.

        ai_len = 0 # 모음의 갯수 연산
        for aski in result_lst: # 결과값을 순회하며
            if aski in aieou_set: # 모음이 있을 때마다
                ai_len += 1 # 모음 갯수에 1개씩 더해줌

        # 4. 출력
        if ai_len and L - ai_len >= 2: # 만약 모음이 있고 자음 또한 2개 이상 있을 때
            print(''.join(map(chr, result_lst))) # 조건에 맞게 변환 후 출력.

    # 3-2. 재귀:
    # z의 askii 값이 124이므로 124까지만 순회
    for i in range(idx, 124):
        if aski_list[i]: # 만약 특정 알파벳이 남았다면

            aski_list[i] = 0 # 특정 알파벳을 사용 처리 후
            result_lst.append(i) # 결과 리스트에 삽입.

            back_track(i+1, length + 1) # '오름차순' 정렬해야 하므로 idx +1, 길이가 늘어났으니 length+1 후 재귀

            result_lst[:] = result_lst[:-1] # == result_lst.pop()
            aski_list[i] = 1

# 소문자 아스키 전체 값:  [97, 122]
# set으로 사용하면 시간을 더 절약할 수 있다.


# 1. 입력.
# L : 암호의 길이
# C : 주어진 알파벳의 종류
L, C = map(int, input().split())

# 2. 선언
aski_list = [0] * 128 # 1) 아스키 리스트
aieou_set = {97, 101, 105, 111, 117} # 2) 모음들의 아스키 값을 모은 집합
result_lst = [] # 결과값 입력받을 리스트

# 1 - 1. 입력 (2)
ipt = list(map(ord, input().split())) # 값을 입력 받은 뒤 askii 값으로 변환 후
for aski in ipt: # 모든 값들을 순회하며
    aski_list[aski] = 1 # askii리스트에 '있음' 표시

# 3. 연산
back_track()