알고리즘

[백준] 1759 암호 만들기 - 골드 5

swanzzz 2025. 4. 7. 20:16
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • 브루트포스, 조합

1. 문제 설명

 

위 설명처럼 
C개의 문자가 주어질 때 L개로 만들 수 있는 암호를 만들건데 이 암호는 사전순으로 정렬되어 출력되며 최소 2개의 자음과 1개의 모음으로 구성되어야 합니다.

 

위 설명처럼 abc는 암호가 되지만 bac는 사전순이 틀려서 되지 않는 암호이고

abc는 되지만 bcd는 안되는 이유는 모음이 포함되지 않아서 안되는 것입니다.

 

이러한 조건을 고려할 때 출력 가능한 모든 암호를 사전순서로 출력하는 프로그램을 작성해야 합니다.

[제한사항]

  • 시간 제한 2초
  • 메모리 제한 128MB
  • 3 ≤ L ≤ C ≤ 15
  • 주어진 문자는 모두 소문자
  • 중복은 없음

2. 접근 방식

 

문제 설명만 보면 순열과 조합을 이용해 출력가능한 모든 경우의 수를 구하고 거기에 조건만 추가하면 되는 문제 같습니다.

 

우선 조합을 구해야 합니다.

 

파이썬의 경우 itertools의 combinations 라는 라이브러리를 활용해 모든 조합을 구할 수 있습니다.

 

이 조합에는 입력받은 words에 L개 만큼 단어를 넣어서 조합을 구하고 그 조합중 조건에 맞는 조합만 출력하면 될 것입니다.

3. 코드

import sys
from itertools import combinations

input = sys.stdin.readline

# 입력
L, C = map(int, input().split())
words = list(map(str, input().split()))

# 조합 만들기, 사전 순서로 출력하기 위해 sorted로 정렬
answer = list(combinations(sorted(words), L))

# 입력받은 조합들 중 출력가능한 조합 찾기
# 출력가능 조건은 자음 최소 2개, 모음 최소 1개
for ans in answer:
    consonants = 0  # 자음의 개수
    vowels = 0      # 모음의 개수

    # 브루트포스 탐색을 통해 모든 조건을 탐색
    for alphabet in ans:
        if alphabet in "aeiou":     # 모음의 경우 판단 하 증가
            vowels += 1
        else:
            consonants += 1
    
    # 출력가능한 조건인 경우 출력
    if consonants >= 2 and vowels >= 1:
        print(*ans, sep="")

[코드 설명]

import sys
from itertools import combinations

input = sys.stdin.readline

# 입력
L, C = map(int, input().split())
words = list(map(str, input().split()))

# 조합 만들기, 사전 순서로 출력하기 위해 sorted로 정렬
answer = list(combinations(sorted(words), L))

 

파이썬 itertools 의 combinations를 활용해 출력 가능한 모든 조합을 우선 만들어 줍니다.

 

순열로 만들 경우 중복도 포함되기 때문에 중복을 제거한 출력 가능한 모든 조건인 조합을 이용했습니다.

 

combinations로 생성한 조합을 사전순서에 맞춰 정렬을 실시합니다.

 

그럼 예를 들어 입력이 a t c i s w 로 들어오면 a t c i 를 선택하고 정렬하여 a c i t 로 정렬하게 됩니다.

 

이런식으로 모든 출력가능한 4자리 비밀번호 조합을 만들고 정렬을 해주는 것입니다.

# 입력받은 조합들 중 출력가능한 조합 찾기
# 출력가능 조건은 자음 최소 2개, 모음 최소 1개
for ans in answer:
    consonants = 0  # 자음의 개수
    vowels = 0      # 모음의 개수

    # 브루트포스 탐색을 통해 모든 조건을 탐색
    for alphabet in ans:
        if alphabet in "aeiou":     # 모음의 경우 판단 하 증가
            vowels += 1
        else:
            consonants += 1
    
    # 출력가능한 조건인 경우 출력
    if consonants >= 2 and vowels >= 1:
        print(*ans, sep="")

 

이제 생성된 answer에는 앞서 설명한 것 처럼 [acis, acit, ...] 이렇게 모든 조합이 배열에 들어간 상태로 정렬되어 있습니다.

 

이 배열을 탐색하며 ans에 담긴 배열 의 글자를 alphabet로 검사하는 겁니다.

 

자음의 개수는 consonants로 세어주고 모음의 개수는 vowels로 세어줍니다.

 

만약 탐색한 알파벳이 aeiou 중 하나라면 모음의 개수를 늘리고 아니라면 자음의 개수를 늘려줍니다.

 

이렇게 해서 자음이 최소 2개이상이고, 모음이 최소 1개 이상인 경우 출력합니다.

 

출력할 때는 배열을 풀어서 출력하는 에스터리크스를 활용하는데 이러면 공백이 추가되어 출력되니 print 조건 중 sep를 활용해 공백을 제거해 주었습니다.

4. 결과

 

[회고]

 

사실 그렇게 어려운 문제는 아니었습니다.

 

문제 설명에 보면 브루트포스, 조합론, 백트래킹 등이 설명되는데 이는 combinations를 직접 구현하는 경우입니다.

 

물론 직접 해당 코드를 구현할 수도 있지만 파이썬 라이브러리에 combinations로 조합을 만들어 주는 라이브러리가 있고 이를 활용하면 쉽게 해결할 수 있습니다.

 

직접 구현한다면 조금 복잡할 수 있습니다.

combinations를 직접 구현하면 다음과 같이 구현될 것입니다.

def combination(arr, r):
    # 1.
    arr = sorted(arr)

    # 2.
    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

    	# 3.
        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for nxt in range(start, len(arr)):
            chosen.append(arr[nxt])
            generate(chosen)
            chosen.pop()
    generate([])


>>> combination('ABCDE', 2)
>>> combination([1, 2, 3, 4, 5], 3)

출처 https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

 

코드의 동작을 살펴보면 선택한 chosen의 길이가 입력한 r이 되면 출력하고 종료합니다.

 

그게 아닌 경우 chosen에 arr의 값을 더해 새로운 배열을 생성하는데 start를 이용해 출력의 범위를 조정합니다.

 

start의 경우 마지막으로 chosen에 입력된 값의 index 위치를 가져와 해당 값에 + 1을 해주는데 없다면 해당 위치를 기준으로 출력범위를 조절합니다.

 

값을 더한경우 generate 함수를 재귀로 실행해 chosen의 길이가 r이 될 때까지 반복하는 거죠

 

이 방법을 사용해도 결과는 동일합니다.

 

조합을 생성하고 출력대신 정답배열에 값을 더해줍니다.

 

그 후 정답배열을 탐색하며 조건에 맞는 경우만 출력해주면 됩니다.

 

이번 문제에서 1번 틀렸던 이유는 문제의 조건을 제대로 살피지 않고 예시 입력만 보고 문제를 풀려고 해서 였습니다..

 

문제의 예시를 보고 단순히 조합만 사용하면 바로 예시가 나오겠는데? 싶어서 조합을 이용해 코드를 작성하고 문제를 풀려했더니 11%에서 틀렸었습니다.

 

그걸보고 아 조건이 더 있구나 싶어서 문제를 다시 자세히 읽었고, 문제의 조건에서 자음과 모음의 개수가 정해져 있다는 것을 알 수 있었습니다.

 

이러면 안되지만 문제를 자주 풀고 많이 풀다보니 이렇게 짧게 문제를 보고 푸는 습관이 생겨버린것 같습니다.

 

다음부터 문제를 풀 때는 꼭 조건을 하나씩 다 확인하고 제대로 풀 수 있도록 해야겠습니다.

 

또 글 작성은 하지 않았지만 하루 1일 1문제를 해결하려고 계속 노력중입니다.

반응형