[백준] 1759 암호만들기 (python 파이썬)

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

1759번: 암호 만들기

---

처음에는 itertools 라이브러리를 사용하여 순열을 구하고, 각 순열마다 검사하는 방법으로 했는데 시간초과 되었다.

생각해 보면 최대 경우가 15P15까지 나오므로 이 방법은 당연히 아니었다.

 

암호를 판별하는 방식이 아닌 처음부터 암호를 조건에 맞게 만드는 방법으로 문제를 풀어 해결하였다.

---

아이디어

1. 암호 조건

• 암호에 있는 알파벳을 증가하는 순서(aescend)로 배열되었다.
• 암호에는 모음 1개 이상, 자음 2개 이상으로 이루어져 있다.

2. 백트래킹

• 백트래킹 알고리즘을 사용하여 알파벳이 증가하는 순서로 암호를 생성해 준다.
• 암호문의 길이가 L이 되면 자음과 모음 개수를 확인해 준다.
• 조건이 맞으면 암호문을 출력해 준다.

---

전체 코드

vowel = ['a', 'e', 'i', 'o', 'u']

L, C = map(int, input().split())
words = input().split()

words.sort() 

def check(arr):
    v_count, c_count = 0, 0 # 모음 개수, 자음 개수

    for i in arr:
        if i in vowel:
            v_count += 1
        else:
            c_count += 1

    if v_count >= 1 and c_count >= 2:
        return True
    else:
        return False

def backtracking(arr):

    if len(arr) == L:
        if check(arr):
            print("".join(arr))
            return

    for i in range(len(arr), C):
        if arr[-1] < words[i]:
            arr.append(words[i])
            backtracking(arr)
            arr.pop()

for i in range(C - L + 1):
    a = [words[i]]
    backtracking(a)

---

코드 설명

vowel = ['a', 'e', 'i', 'o', 'u']

L, C = map(int, input().split())
words = input().split()

words.sort()

나중에 암호문의 모음, 자음을 확인하기 위해 모음으로 이루어진 리스트를 하나 선언해 둔다.

주어진 입력을 받고, 주어진 문자들은 알파벳순으로 정렬(sort())한다.

 

for i in range(C - L + 1):
    a = [words[i]]
    backtracking(a)

그리고 각 알파벳을 시작으로 backtracking함수를 호출한다.

이때 암호문의 길이(L)를 만들 수 없는 알파벳은 제외한다.

예를 들어 예제에 있는 알파벳을 보면 a, c, i까지 암호문을 만들 수 있고 그 이후로는 암호문 길이를 만들지 못하니까 제외한다.

 

def backtracking(arr):

    if len(arr) == L:
        if check(arr):
            print("".join(arr))
            return

    for i in range(len(arr), C):
        if arr[-1] < words[i]:
            arr.append(words[i])
            backtracking(arr)
            arr.pop()

backtracking함수는 위와 같다.

먼저 탈출 조건으로 암호 리스트의 길이가 L이 되면 check함수를 호출해 모음, 자음을 확인해 준다.

조건이 참이면 암호를 출력하고 return 해준다. join 메서드를 써서 간편하게 출력해 줄 수 있다.

 

아직 길이가 L이 아니면 알파벳을 하나씩 추가해 준다. if문을 사용해 암호문이 ascend 하게 알파벳을 추가해 준다.

 

def check(arr):
    v_count, c_count = 0, 0 # 모음 개수, 자음 개수

    for i in arr:
        if i in vowel:
            v_count += 1
        else:
            c_count += 1

    if v_count >= 1 and c_count >= 2:
        return True
    else:
        return False

check함수는 위와 같다.

입력받은 리스트(arr)를 한번 스캔하여 모음과 자음 개수를 확인하고 조건에 맞으면 True,

조건에 맞지 않으면 False를 리턴해준다.