[백준 알고리즘] 1759번: 암호 만들기 (Python / 파이썬)

문제 링크

1759번: 암호 만들기

 

문제 접근

재귀함수를 만들어 해결하였다.

암호의 길이가 L이고 알파벳순으로 암호가 나와야 하기 때문에, 문자가 C개 주어진다면 문자열을 순회하며 인덱스가 L-C+1인 것까지 탐색하며 재귀함수를 호출한다.

L = 4, C = 6 

a t c i s w

다음과 같이 주어진다면 먼저 이것을 정렬하여 알파벳순으로 만들면

a c i s t w

정렬된 상태에서 0 ~ L-C+1 인덱스를 탐색하면 a 또는 c 또는 i 로 시작하는 알파벳순의 문자열만을 만들 수 있다.

(i로 시작하는 것은 istw 밖에 존재할 수 없는 것이다.)

시작점을 재귀함수의 파라미터 배열 안에 넣고 선택되지 않은 알파벳들을 넣고, 다시 함수 호출을 하고 선택 배열에서 다시 뺀다.

 

주의할 점은 모음과 자음 수를 체크해야 하는데,

파라미터로 전달해서 체크한다. 이때도 선택 배열과 같이 모음과 자음 변수를 카운트해주고 함수를 호출하면 다시 값을 내려줘서 원상복귀 시켜주어야 한다.

 

정답 코드 (주석 o)

# 1759번: 암호 만들기

import sys


def func(select, consonant, vowel):
    if len(select) == l and vowel >= 1 and consonant >= 2: # 출력 조건: 암호 수 만족 및 최소 자음 모음 수 만족
        print(''.join(map(str, select)))
    for i in range(1, c): # 시작점은 넣어뒀기 때문에 1부터 시작
        if a[i] not in select and a[i] > select[-1]: # 조건 : 선택 배열에 없는 알파벳 및 마지막 것보다 다음 순서
            select.append(a[i]) # 선택 배열에 추가
            if a[i] in vowels:
                vowel += 1 # 모음 카운트
                func(select, consonant, vowel)
                vowel -= 1 # 원상복귀
            else:
                consonant += 1 # 자음 카운트
                func(select, consonant, vowel)
                consonant -= 1 # 원상복귀
            select.pop() # 원상복귀


l, c = map(int, sys.stdin.readline().split())
a = list(sys.stdin.readline().split())
a = sorted(a)

vowels = ['a', 'e', 'i', 'o', 'u']
for i in range(c - l + 1):
    if a[i] in vowels:
        func([a[i]], 0, 1)
    else:
        func([a[i]], 1, 0)

주석을 보면 잘 이해할 수 있다.

정답 코드 (주석 x)

# 1759번: 암호 만들기

import sys


def func(select, consonant, vowel):
    if len(select) == l and vowel >= 1 and consonant >= 2:
        print(''.join(map(str, select)))
    for i in range(1, c):
        if a[i] not in select and a[i] > select[-1]:
            select.append(a[i])
            if a[i] in vowels:
                vowel += 1
                func(select, consonant, vowel)
                vowel -= 1
            else:
                consonant += 1
                func(select, consonant, vowel)
                consonant -= 1
            select.pop()


l, c = map(int, sys.stdin.readline().split())
a = list(sys.stdin.readline().split())
a = sorted(a)

vowels = ['a', 'e', 'i', 'o', 'u']
for i in range(c - l + 1):
    if a[i] in vowels:
        func([a[i]], 0, 1)
    else:
        func([a[i]], 1, 0)

---

고찰

파이썬의 in 연산자와, 문자열 비교가 유용하게 쓰였던 것 같다. 원래는 아스키 코드를 써야 하나 싶었는데 안 쓰고 해결할 수 있었다.

그리고 다시 보니

      vowel += 1 # 모음 카운트
      func(select, consonant, vowel)
      vowel -= 1 # 원상복귀

이렇게 작성했는데, 이해는 이게 더 잘 되지만

    func(select, consonant, vowel + 1)

와 같이 줄이는 게 더 간결한 것 같다.

---