[BAEKJOON]1759 암호 만들기 - python

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Gold5
• 문제내용:
  • 서로 다른 알파벳 L과 C개의 문자를 주어진다.
  • 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다.
  • 정렬 되어있다.
  • 조건에 맞는 암호들을 모두 출력해라
• 사이트 주소: https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

그리고 백트레킹으로 조합을 구하는것라서 조합을 구현 하는 방법은 아래 사이트에서 확인 해보면 된다.

https://jih3508.tistory.com/116

[BAEKJOON]15663 N과 M (9)

문제 접근 방법

 이번 문제는 조합 + 조건에 맞는 암호를 구하면 된다. 알파벳 순서 대로 정렬후 백트레킹 알고리즘으로 조합 L개를 구한 다음 모음 최소 한 개 이상와 자음 2개 이상를 구하면 된다. 모음 최소 한개 와 자음 2개는 알파벳 문자열에 모음 개수를 구한뒤 전체 문자열 길이와 모음 개수를 빼서 2개 이상일때 출력하는 형식으로 구현 하면 끝이다.

정리

1. 문제에 주어진 알파벳을 정렬한다.
2. 백트레킹 알고리즘으로 조합을 구현한다.
3. 모음 개수를 구하고 모음 개수 1개 이상과  전체 문자열과 모음 개수를 빼서 2개 이상이면 출력한다.

Code

 이번에는 python에서 2가지 방법으로 풀것이다. 첫번째는 순수 백트레킹으로 구현한 방법이고 2번째는 combination 라이브러리를 사용하는 방법이다. 2가지 방법을 익히면 유용하게 쓰일것이다.

 

백트레킹으로 구현 한것

# 모음 개수 구하는 함수
def check_password(password):
    count = 0
    for char in password:
        if char in {"a", "e", "i", "o", "u"}:
            count += 1
    return count
        

def make_password(depth, password):
    if len(password) == L:        
        count = check_password(password)
        if count >= 1 and L - count >= 2:
            print(password)
        return
    for i in range(depth, C):
        make_password(i + 1, password + alpabet[i])


L, C = map(int, input().split())
alpabet = sorted(list(input().split()))
make_password(0, "")

combinations으로 구현 한것

from itertools import combinations

def check(a):
    count = 0
    for al in data:
        count += al in included
    return count

L, C = map(int, input().split())
alpaber = sorted(list(input().split()))
included = set({'a', 'e', 'i', 'o', 'u' })
result = []
for data in combinations(alpaber, L):
    count = check(data)
    if(count >=1 and L - count >= 2):
        result.append(sorted(data))

result.sort()
for data in result:
    print(''.join(data)