[BOJ] 1759 - 암호 만들기

사용 언어: Python3

문제

백준 1759

문제 풀이 핵심 아이디어

• C개의 문자들이 주어졌을 때, 가능한 L 길이의 암호를 모두 찾아야 합니다.
• 따라서 C개의 문자들 중에서 L개를 선택하는 모든 “조합”을 고려해야 합니다.
  • 파이썬의 조합(combination) 라이브러리를 사용하면 간단히 해결할 수 있습니다.
  • 혹은 DFS를 이용하여 조합 함수를 구현할 수 있습니다.

풀이

첫 번째

# L: 캐릭터 수, C: 가능성 있는 문자 수
L, C = map(int, input().split())
lst = [x for x in input().split()]

# 증가하는 순서로 정렬
lst.sort()

# 6개중 4개 조합 (combination, 순서X)
# 6C4 -> L=4, C=6

visited = [False] * C

def printAns():
  res = []
  for i in range(C):
    if visited[i]:
      res.append(lst[i])
  # 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다.
  vowels = [k for k in res if k=='a' or k=='e' or k=='i' or k=='o' or k=='u']
  if len(vowels) >= 1 and len(res)-len(vowels) >= 2:
    print(''.join(res))

def dfs(idx, cnt):
  if cnt == L:
    printAns()
    return
  for i in range(idx, C):
    if visited[i]:
      continue
    visited[i] = True
    dfs(i, cnt+1)
    visited[i] = False

dfs(0,0)

• 성공!

조합(combination) 라이브러리 사용

from itertools import combinations # ✅

vowels = ('a', 'e', 'i', 'o', 'u')
L, C = map(int, input().split())
lst = input().split()
lst.sort()

# 길이가 L인 모든 암호 조합을 확인
for x in combinations(lst, L): # x는 튜플
  cnt = 0 # 모음 개수
  for val in x:
    if val in vowels:
      cnt += 1
  # 최소 한 개의 모음과 최소 두 개의 자음이 있는 경우
  if cnt >= 1 and L-cnt >= 2:
    print(''.join(x))

dfs 이용해 조합 직접 구현

import copy

result = []
string = []
visited = []

# 조합(combination) 함수 구현
def dfs(array, length, idx):
  # 길이가 length인 모든 조합 찾기
  if len(string) == length:
    result.append(copy.deepcopy(string))
    return
  # 각 원소를 한 번씩만 뽑도록 구성
  for i in range(idx, len(array)):
    if i in visited:
      continue
    string.append(array[i])
    visited.append(i)
    
    dfs(array, length, i+1)
    
    string.pop()
    visited.pop()

vowels = ('a', 'e', 'i', 'o', 'u')
L, C = map(int, input().split())

# 가능한 암호를 사전순 출력
lst = input().split()
lst.sort()

dfs(lst, L, 0)

# 길이가 L인 모든 암호 조합을 확인
for x in result:
  cnt = 0 # 모음 개수
  for val in x:
    if val in vowels:
      cnt += 1
  # 최소 한 개의 모음과 최소 두 개의 자음이 있는 경우
  if cnt >= 1 and L-cnt >= 2:
    print(''.join(x))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기