[BOJ] 백준 1759 암호 만들기 - Python/Java

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

1759번: 암호 만들기

 

해설

주어진 문자열의 길이가 최대 15밖에 되지 않기 때문에 모든 경우를 완전탐색할 수 있는 문제입니다. 다시 말해서, 각 문자를 비밀번호에 포함/미포함으로 완전 탐색을 해도 2^15번만에 모든 경우를 탐색할 수 있는 것이죠.

 

구체적으로 문제의 조건을 들여다보겠습니다.

 

문제에서는 비밀번호가 "1) 사전식으로 오름차순 정렬되어 있다. 2) 자음의 개수는 2자 이상이다. 3) 모음의 개수는 1자 이상이다."라는 조건을 걸고 있습니다.

 

따라서, 맨 처음에 입력받은 문자열들을 오름차순 정렬해주게 되면 인덱스를 하나씩 증가시켜 완전탐색을 했을 때 완성되는 비밀번호도 자연스레 오름차순 정렬이 됩니다.

 

그리고 완전탐색을 구현할 때는 재귀 함수를 이용했는데요. 재귀함수의 매개변수로 현재 비밀번호, 현재 읽을 문자열의 인덱스, 자음의 개수, 모음의 개수 총 네 가지를 받았습니다. 처음에 재귀함수를 호출할 때는 빈 문자열, 0, 0, 0을 파라미터로 넘기고 매 재귀함수의 콜마다 인덱스를 1 증가시키고, 현재 문자가 자음인지 모음인지에 따라 자음의 개수를 늘리거나 모음의 개수를 늘리는 식으로 재귀함수를 호출했습니다.

 

다만, 여기서 현재 문자를 포함하지 않는 경우도 고려해야 하기 때문에 단순히 인덱스만 1 증가시킨 재귀함수의 호출도 해주어야 합니다.

 

풀이를 읽어보시면 바로 이해가 되실 것 같습니다.

 

풀이 - 파이썬

def makePassword(passwd, idx, p, q):
    # 모든 문자를 탐색했을 때
    if idx == len(letters):
        # 길이가 l이고 자음은 2자, 모음은 1자 이상이라면 성공
        if len(passwd) == l and p >= 2 and q >= 1:
            print(passwd)
        return
        
    curr = letters[idx]
    # 현재 문자를 포함, 미포함 둘 다 진행한다.
    # 포함한다면 현재 passwd에 문자를 더하고, 인덱스와 자음 or 모음의 개수를 증가시킨다.
    if curr in "aeiou":
        makePassword(passwd+curr, idx+1, p, q+1)
        makePassword(passwd, idx+1, p, q)
    else:
        makePassword(passwd+curr, idx+1, p+1, q)
        makePassword(passwd, idx+1, p, q)

l, c = map(int, input().split())
# 주어진 문자를 오름차순으로 정렬
letters = sorted(list(input().split()))
makePassword("", 0, 0, 0)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B_1759 {
    static int l, c;
    static String[] letters;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        letters = br.readLine().split(" ");
        // 주어진 문자를 오름차순으로 정렬
        Arrays.sort(letters);

        StringBuilder sb = new StringBuilder();
        makePassword("", 0, 0, 0);
    }

    public static void makePassword(String passwd, int idx, int p, int q){
        // 모든 문자를 탐색했을 때
        if (idx == c){
            // 길이가 l이고 자음은 2자, 모음은 1자 이상이라면 성공
            if (passwd.length() == l && p >= 2 && q >= 1){
                System.out.println(passwd);
            }
            return;
        }

        String curr = letters[idx];
        // 현재 문자를 포함, 미포함 둘 다 진행한다.
        // 포함한다면 현재 passwd에 문자를 더하고, 인덱스와 자음 or 모음의 개수를 증가시킨다.
        if("aeiou".contains(curr)){
            makePassword(passwd+curr, idx+1, p, q+1);
            makePassword(passwd, idx+1, p, q);
        }
        else{
            makePassword(passwd+curr, idx+1, p+1, q);
            makePassword(passwd, idx+1, p, q);
        }
    }
}