[BOJ] 1759 - 암호 만들기

gmelan·2022년 4월 16일
0

알고리즘 트레이닝

목록 보기
10/14

풀어보기

접근

조건에 맞는 암호를 사전순으로 출력한다.

문제를 본 순간 N과 M(2)과 비슷한 문제라는 생각이 들었다. 따라서 위 문제의 접근법을 참고하여, 재귀를 통해 풀어보기로 마음을 먹었다.
N과 M(2) 문제와 다른 점은 출력 문자열에 추가적인 조건(자/모음 개수 제한)이 붙어 있다는 것이다.
이 조건들을 어떻게 해야 할지 고민하다가, 일단 후보 선정 직전에 조건 충족 여부를 확인하는 식으로 코드를 짜보기로 하였다.

코드

from sys import stdin

def make_str(next_idx, jaum, moum):
    global L, C, alphabets, answer, passwd

    if len(passwd) == L and jaum <= 0 and moum <= 0:
        answer.append(passwd)
        return

    if next_idx == C:
        return

    for i in range(next_idx, C):
        is_moum = alphabets[i] in ('a', 'e', 'i', 'o', 'u')
        passwd += alphabets[i]
        make_str(i + 1, jaum-1 if not is_moum else jaum, moum-1 if is_moum else moum)
        passwd = passwd[:-1]


L, C = map(int, stdin.readline().split())
alphabets = stdin.readline().strip().split()
alphabets.sort()

passwd = ""
answer=[]
make_str(0, 2, 1)

for i in answer:
    print(i)

jaum, moum은 생각하는 그 의미가 맞다(...). 기본적인 틀은 N과 M(2)와 같으나, 입력이 정렬되어 있지 않으므로 정렬을 먼저 시행한다(이 방법으로 사전순 출력을 하기 위해서는 원 데이터가 정렬되어 있어야 함). 또 후보 문자열을 만들 때 자음, 모음 조건을 감시하다가 완성 시(len(passwd) == L) 조건 충족 여부를 같이 확인하고 있다.

시사점

난이도가 꽤 높은 문제일 줄 알았으나 막상 이전 문제에서 썼던 전략을 응용하니 금방 풀려 조금 당황했던 문제였다. 문제를 풀고 피드백을 하는 것이 학습에 도움이 됨을 스스로 입증할 수 있었다. 군생활이라는 악조건 속에서 조금씩이라도 발전하고 있다는 것이 그저 감사할 따름이다.

0개의 댓글