Baekjoon Training #1759

---

#1759 암호 만들기

combination 활용

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

l, c = map(int, input().split())
letters = list(map(str, input().split()))  
# 사전순으로 정렬
letters.sort()
# 가능한 조합 전부 생성
pos_code = combinations(letters, l)
# 모음 리스트 생성
vowel = ['a', 'e', 'i', 'o', 'u']
# 모음 1개 이상, 자음 2개 이상인 코드만 출력
for code in pos_code:
    vowel_num = 0
    const_num = 0
    for i in range(l):
        if code[i] in vowel:
            vowel_num += 1
        else:
            const_num += 1
    if vowel_num >=1 and const_num >=2:
        ans_code = ''.join(code)
        print(ans_code)

파이썬의 위력을 알 수 있는 코드이다.

브루트포스 알고리즘 문제를 Library와 내장 함수를 적절히 이용하여 직관적이고 간단한 코드를 완성하였다.

우선 sort()함수로 사전순 정렬을 해주고 combinations()함수를 이용하여 가능한 조합을 전부 만들었다. 조합이 필요한 브루트포스 알고리즘에서 굉장히 유용하게 쓰이는 함수이다. combinations(리스트, 조합의 길이)꼴로 수행할 수 있다. 추가적으로 permutations() 함수로는 순열을 만들 수 있다. 조합은 중복이 없는 반면 순열은 중복이 존재하는 경우의 수이다.

브루트포스 알고리즘 문제이므로 DFS, BFS, 백트래킹 중 하나로 한번더 풀어보고자한다.

---

백트래킹

import sys
input = sys.stdin.readline

l, c = map(int, input().split())
letters = list(map(str, input().split()))
# 사전순으로 정렬
letters.sort()
# 모음 리스트 생성
vowel = ['a', 'e', 'i', 'o', 'u']
# 정답 코드 담아둘 리스트
ans_code = []
# back_tracking 함수 생성
def back_tracking(cnt, idx):
    # 조건 체크
    if cnt == l:
        # 모음, 자음 개수 확인
        vowel_num, const_num = 0, 0
        for i in range(l):
            if ans_code[i] in vowel:
                vowel_num += 1
            else:
                const_num += 1

        # 모음 1개 이상, 자음 2개 이상
        if vowel_num >= 1 and const_num >= 2:
            ans = ''.join(ans_code)
            print(ans)
        return

    # 반복문을 통해 암호 생성
    for i in range(idx, c):
        ans_code.append(letters[i])
        back_tracking(cnt + 1, i + 1) # 재귀를 통한 백트래킹
        ans_code.pop()

back_tracking(0, 0)

재귀를 활용한 백트래킹 알고리즘을 이용한 코드이다. 기본적인 코드 흐름은 위의 코드와 같지만 combinations()함수를 이용하여 간다한게 해결하던 문제를 for문을 이용하여 직접 list에 담아가며 조사를 해야한다.

---