[백준 1759 골드5] 암호 만들기

www.acmicpc.net/problem/1759

1759번: 암호 만들기

해결방안

• 백트래킹 문제

• 조합에 대한 이해가 있으면 좀 더 쉽게 풀 수 있음
• 정렬과 예외 처리
• 참고 문제 풀이
  • N과 M (2)

알고리즘

1. l, c를 받아옴

2. 문자열을 리스트로 만들어서 정렬 시킴
   
   1. 문제의 조건에 암호는 증가순이라고 쓰여있기 때문에 알파벳 순으로 정렬
3. l 크기 만큼 배열 생성
   1. 배열을 만드는 이유는 굳이 새로운 리스트에 append, pop하는것을 할 필요가 없기 때문
   2. 배열은 어차피 다 채워질 것 이기 때문에 내용은 아무거나 상관 없음
4. 백트래킹을 위한 함수 생성
   1. 인자로 index와 cnt 를 받음
      1. index는 재귀 함수에서 반복문을 시작할 부분을 나타냄
      2. cnt는 문자열의 총 길이를 나타냄
   2. cnt가 l과 같을 경우, 값을 result 리스트에 추가시킴
      1. cnt가 l과 같다는 것은 현재 총 문자열의 길이가 구하고자 하는 조합의 길이와 같다는 것을 의미
      2. result에 추가하는 이유는 문제의 조건에 있는 최소 1개의 모음, 2개의 자음을 체크하기 위함
   3. index부터 전체 문자열의 길이까지 반복문 수행
      1. 배열의 cnt에 문자열의 i 번째를 넣음
      2. i와 cnt를 하나씩 증가시켜서 재귀함수 실행
5. 백트래킹 함수는 인자가 (0, 0) 부터 실행
6. result에 저장된 리스트를 반복문을 이용해서 예외 처리
   1. 각각의 원소들을 가지고, 다시 원소들의 글자에 모음이 들어가 있는지 확인하고 모음의 갯수 저장
   2. 각 원소들의 모음의 갯수가 1개 이상이고 l에서 2만큼 뺀것보다 모음의 갯수가 작을 경우 출력
      • l에서 2만큼 뺀것보다 모음의 갯수가 작다는 것은 반대로 말하면 자음의 갯수가 최소 2개라는 것을 의미

핵심 팁

• 코드로만 보기 보다는 그림을 그려보며 함수를 따라가보면 조금 더 이해가 쉬움
• 백트래킹 방식 말고 라이브러리를 이용해도 가능
  
  • from itertools import combinations
• 모음과 자음의 갯수를 예외 처리 시켜주어야 함
• 알파벳 순이기 때문에 미리 정렬 필요

일반 백트래킹식 풀이

# 조합문제
# 암호는 증가순 => 알파벳으로 정렬하고 조합 하면 됨
# 문자의 종류는 c가지, 최소 1개의 모음, 2개의 자음
import copy
l, c = map(int, input().split())
ch = list(input().split())
ch.sort()
arr = ['l'] * l
result = []
# n 과 m 풀듯이 풀면 될 듯
def pwd(index, cnt):
    if cnt == l:
        result.append(copy.deepcopy(arr))
        return
    for i in range(index, c):
        arr[cnt] = ch[i]
        pwd(i + 1, cnt + 1)

pwd(0, 0)
vowels = ['a', 'e', 'i', 'o', 'u']
for p in result:
    count = 0
    for i in p:
        if i in vowels:
            count += 1
    # 모음이 1개 이상 이고 모음이 전체에서 2개 즉 자음의 갯수보다 작을 경우라는 것은 자음이 2개 이상이라는 의미
    if count >= 1 and count <= l - 2:
        print("".join(p))

 

조합 라이브러리 이용한 풀이

# 조합문제
# 암호는 증가순 => 알파벳으로 정렬하고 조합 하면 됨
# 문자의 종류는 c가지, 최소 1개의 모음, 2개의 자음
from itertools import combinations
l, c = map(int, input().split())
ch = list(input().split())
ch.sort()
result = []
vowels = ['a', 'e', 'i', 'o', 'u']
# 라이브러리 사용
for comb in combinations(ch, l):
    count = 0
    for i in comb:
        if i in vowels:
            count += 1
    if count >= 1 and count <= l - 2:
        print("".join(comb))

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public