[백준 1759번] 암호 만들기

박형진·2023년 2월 25일
0

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


1. 코드

import sys
from collections import defaultdict


def dfs(cnt, idx, path):
   if cnt == n:
       ja = mo = 0
       for char in path:
           if char in ['a', 'e', 'i', 'o', 'u']:
               mo += 1
           else:
               ja += 1

       if mo >= 1 and ja >= 2:
           print(''.join(path))
       return

   for i in range(idx, len(arr)):
       if not visited[i]:
           visited[i] = True
           dfs(cnt+1, i+1, path+[arr[i]])
           visited[i] = False


n, m = map(int, sys.stdin.readline().rstrip().split())
arr = sorted(map(str, sys.stdin.readline().rstrip().split()))
visited = defaultdict(bool)
dfs(0, 0, [])

추가 코드

import sys


l, c = map(int, sys.stdin.readline().rstrip().split())
lst = sorted(list(map(str, sys.stdin.readline().rstrip().split())))
answer = []
tbl = [0]*128  # 테이블을 사용하여 매번 if문을 통해 모음 검사 코드 제거
for ch in 'aeiou':
    tbl[ord(ch)] = 1

def dfs(idx, cnt, tst):
    if idx == c:
        if len(tst)==l and cnt>=1 and l-cnt >= 2:
            answer.append(tst)
        return
	
    # 2^15는 기껏해야 3만 언저리 -> 포함/불포함 방식
    dfs(idx + 1, cnt + tbl[ord(lst[idx])], tst + lst[idx])  # 현재 알파벳을 포함
    dfs(idx + 1, cnt, tst)  # 현재 알파벳을 불포함


dfs(0, 0, '')
for i in answer:
    print(i)

2. 후기

C개의 문자들을 알파벳 순으로 정렬한 후 조합을 구현하면 알파벳이 암호에서 증가하는 순서로 배열 조건을 만족시키는 path값을 얻을 수 있다.

추가 코드는 https://www.youtube.com/watch?v=3WS6LMgnYzA 참조.

profile
안녕하세요!

0개의 댓글