백준_1759 (암호 만들기_골드5_브루트포스_combinations) 호석 완전탐색3

• 링크 : https://www.acmicpc.net/problem/1759

---

메모

최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성
각각의 암호 후보들은 알파벳 순서대로 정렬
출력 결과도 모든 후보들을 알파벳 순서대로 정렬한듯

• 신기하게도 골드5인데 10분만에 알고리즘 짜고, 20분(?)만에 코드 짜서 한번에 맞춤

  <핵심은>
  입력받은 알파벳을 일단 sorting시켜야 함 --> 이걸 해야 combinations의 결과가 문제에서 원한 결과로 나옴(permutaions가 아니기 때문)

  그리고 "모음", "자음"이 각각 사용된 횟수를 체크해서, 문제에서 요구한 만큼 사용된 case들만 결과물로 저장

알고리즘

input L, C
arr = [ 입력알파벳들 ]
arr.sort()                     # (개중요) 이걸 미리 해주고 combinations 써야 문제에서 원하는 "정렬"이 수행됨
모음 리스트 =[a,e,i,o,u]
#그외 리스트 = 자음 리스트

for candidate in combinations(arr, L):
    is_모음 = False             # 최소 하나만 있으면 되므로 True False
    is_자음 = 0                 # 2개 이상이어야 하므로

    for i in candidate:
        if i in 모음리스트:
            is_모음 = True
        else:                    # if i in 자음리스트:
            is_자음++
            
    if is_모음 == True and is_자음 >= 2:
        answer.append("".join(map(str, candidate)))

print(answer)

• 입력받은 배열을 sort안해줬을 경우, combinations의 결과
  - 각 문자열이 정렬이 안되어있는 것을 볼 수 있음!
  

---

솔루션 코드 - 내가푼

from itertools import permutations, combinations
import sys
input = sys.stdin.readline

l, c = map(int, input().split())
arr = list(input().split())
arr.sort()
vowels = ['a', 'e', 'i', 'o', 'u']
answer = []

for candidate in combinations(arr, l):
    is_vowels = False
    is_consonants = 0
    
    for i in candidate:
        if i in vowels:
            is_vowels = True
        else:
            is_consonants += 1
            
    if is_vowels == True and is_consonants >= 2:
        answer.append("".join(map(str,candidate)))
        
print("\n".join(answer))

---

솔루션 코드 - 블로그

• 백트래킹 방식 사용했다는데, 관련 공부 좀 해야할듯
• 링크 : https://fre2-dom.tistory.com/454

import sys


def back_tracking(cnt, idx):

    # 암호를 만들었을 때
    if cnt == l:
        # 모음, 자음 체크
        vo, co = 0, 0

        for i in range(l):
            if answer[i] in consonant:
                vo += 1
            else:
                co += 1

        # 모음 1개 이상, 자음 2개 이상
        if vo >= 1 and co >= 2:
            print("".join(answer))

        return

    # 반복문을 통해 암호를 만든다.
    for i in range(idx, c):
        answer.append(words[i])
        back_tracking(cnt + 1, i + 1) # 백트래킹
        answer.pop()


l, c = map(int, sys.stdin.readline().split())
words = sorted(list(map(str, sys.stdin.readline().split())))
consonant = ['a', 'e', 'i', 'o', 'u']
answer = []
back_tracking(0, 0)