1759

날짜 : 2023. 05. 20

사용 언어 : python

 

문제

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

 

 

코드

import sys

def dfs(s, idx):
    if len(s) == L:  # 암호문 가능한 경우
        cnt = 0  # 모음의 개수
        for i in s:
            if i in gat: cnt += 1
        if cnt > 0 and (L-cnt) > 1:
            print(s)
    for i in range(idx, C):
        dfs(s + a[i], i+1)
    return


L, C = map(int, sys.stdin.readline().split())  # 암호문 길이, 알파벳 개수
a = ' '.join(sys.stdin.readline().rstrip()).split()
gat = dict()
a.sort()
for i in a:
    if i in ['a', 'i', 'e', 'o', 'u']:  # 모음 체크
        gat[i] = 1

for i in range(C-L+1):
    dfs(a[i], i+1)

 

 

풀이

- 조건에 맞게 입력받은 후 입력받은 알파벳을 오름차순으로 정렬한다.(암호문은 오름차순이라는 조건)

- 그 다음 암호문에서 최소 1개 모음, 최소 2개 자음이라는 조건이 있기 때문에 상대적으로 적은 모음을 체크하기 위해 해시를 만든다.

- 그 다음 브루트포스를 활용해 DFS를 진행

- 문자열의 길이가 L(출력해야 하는 암호문 길이)인 경우 모음 개수를 체크한 후 출력여부를 결정한다.

- 만약 길이가 되지 않는다면 그 다음 인덱스들을 체크하면서 DFS를 진행

 

 

알게된 점

- itertools를 활용해 combination 라이브러리를 쓸까.. 하다가 직접 구현해보자!! 해서 dfs로 풀었다.

- 뭔가 직접 구현해서 푸니까 뿌듯하다.

 

 

참고 사이트

-