[Algorithm] 1759. 암호 만들기

1759: 암호 만들기(백트래킹)

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

• 문제 티어 : G5
• 풀이 여부 : Solved
• 소요 시간 : 17:49

정답 코드

import sys
input = sys.stdin.readline

L, C = map(int, input().rstrip().split())
candidates = sorted(list(map(str, input().rstrip().split())))

ans = []

def backtrack(start, curr):
  if len(curr) == L:
    aeiou_cnt = sum(1 for c in curr if c in 'aeiou')
    if aeiou_cnt >= 1 and len(curr) - aeiou_cnt >= 2:
      ans.append(curr[:])
      return

  for i in range(start, C):
    curr.append(candidates[i])
    backtrack(i+1, curr)
    curr.pop()

backtrack(0, [])
for a in ans:
  print(*a, sep='')

접근 방식

저번 로또 백트래킹 문제와 거의 동일하다!

검색 시간을 O(1)로 가져가려고 처음에는 모음의 갯수를 계산할 때,

딕셔너리로 모음을 관리했는데! 굳이 그러지 않아도 충분했다…

시간복잡도의 경우,

1. C개 중 L개를 선택하는 조합의 시간복잡도 : $O(C! / (L! * (C-L)!))$
2. 각 조합을 검사하는 시간복잡도 : 조합의 길이만큼 → $O(L)$

따라서 전체 시간복잡도는 $O((C! / (L! * (C - L)!)) * L)$ 이다.

그리고 아주 파이써닉한 코드!

aeiou_cnt = 0
for c in curr:
	if c in 'aeiou':
		aeiou_cnt += 1

위 코드를

aeiou_cnt = sum(1 for c in curr if c in 'aeiou')

이렇게 축약할 수 있다!

배운점 또는 느낀점

은근 조합의 중복을 방지하기 위한 시작점 갱신을 계속 빼먹는 경우가 많다.

중복을 방지하고자 할 때에는 backtrack 함수에 start 값과 curr배열을 함께 넘겨주는 것 잊지 말자!