알고리즘 풀이 - 백준 1759(암호 만들기, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

C개의 알파벳 소문자가 주어질 때, L개의 알파벳으로 암호를 만드는 모든 경우의 수를 출력한다.

암호는 알파벳 사전 순서로만 구성되며, 최소 1개의 모음, 최소 2개의 자음으로 구성된다. 전체 내역은 사전 순으로 출력

 

 

2. 풀이

 

이 문제는 나열된 문자들 C개 중 L개를 선택하여 선택 가능한 경우에 출력하는 문제이다. 그러므로 C개의 문자 중 L개를 선택하는 모든 경우를 다 살펴보아야 한다.

재귀를 이용하는 것이 가장 쉬운 방법인데, 재귀를 이용 시에는 탈출 조건을 정해야 한다.

 

탈출 조건은 다음과 같다.

→ 조건 : L개를 선택한 경우이며 자음이 2개 미만 / 모음이 1개 미만이라면 출력하지 않고 반환 / 그 외의 경우는 출력 후 반환

 

위와 같은 탈출 조건은 손쉽게 생각해볼 수 있다. 그렇다면 함수의 상태는 어떤 값을 전달해야 할까? 그렇다. 위의 탈출 조건에 쓰기 위해서 우선 선택된 자음 개수, 모음 개수, 전체 개수를 알아야 한다.
(물론 전체 개수는 자음 + 모음으로 해도 된다.)

 

이외에도 선택된 자음을 저장하는 배열과, 이전 재귀 함수 내에서 선택된 문자의 위치 또한 전달해야 한다. 왜냐하면, 중복된 숫자는 사용할 수 없고 암호는 오름차순이므로 정렬된 상태라면 반드시 이후의 문자 부터 선택이 가능하기 때문이다!

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.Arrays;

public class Main{
    static int L;
    static int C;
    static char ch[];
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] line = br.readLine().split(" ");
        L = Integer.parseInt(line[0]);
        C = Integer.parseInt(line[1]);
        
        ch = new char[C];
        line = br.readLine().split(" ");
        for(int i=0; i < C; i++){
            ch[i] = line[i].charAt(0);
        }
        // 정렬 수행(사전 순이기 때문)
        Arrays.sort(ch);
        char chosen[] = new char[L];
        
        solve(0, 0, 0, 0, chosen);
        bw.flush();
        br.close();
    }
    
    // parameter로 자음 선택 수, 모음 선택 수, 이전 선택된 문자의 index, 전체 선택된 개수를 전달
    private static void solve(int cons_cnt, int vowel_cnt, int n, int idx, char chosen[]) throws IOException{
    
        
        // 탈출 조건 - L개를 고른 경우, 자음 / 모음의 수 또한 체크!
        if(n == L){
            if(cons_cnt < 2 || vowel_cnt < 1) return;
            
            for(char c : chosen){
                bw.write(c);
            }
            bw.write("\n");
            return;
        }
        
        for(int i=idx; i < C; i++){
            char curr = ch[i];
            chosen[n] = curr;
            
            // 선택된 것이 모음이라면 모음 선택 개수 +1
            if(curr == 'a' || curr == 'e' || curr == 'i' || curr == 'o' || curr == 'u'){
                solve(cons_cnt, vowel_cnt+1, n+1, i+1, chosen);
            // 선택된 것이 자음이라면 자음 선택 개수 +1
            } else {
                solve(cons_cnt+1, vowel_cnt, n+1, i+1, chosen);
            }
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.