1 분 소요

문제

문제 바로가기

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근방법

일반적으로는 자료형 char을 이용했을 문제이지만 여기서는 전부 문자열을 사용했다.

백트래킹을 자음, 모음으로 나누어 2번을 계산하는 방식으로 접근했다.

  • 입력받은 문자를 con, vow에 각각 자음과 모음으로 나누어 저장하고,

  • 자음의 개수와 모음의 개수가 각각 할당될 수 있는 경우의 수를 반복문을 통해 구해주었다.

  • 각각 할당된 개수에서 vowDfs에서는 모음이 선택되는 경우의 수를, conDfs에서는 자음이 선택되는 경우의 수를 구해서 temp에 저장하고, 오름차순 정렬을 하여 result에 추가해주었다.

  • 최종적으로 출력하기 전에 result를 오름차순 정렬을 해서 문제를 해결하였다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int L, C;
    static String vows = "aeiou";
    static List<String> con = new ArrayList<>();
    static List<String> vow = new ArrayList<>();
    static List<String> temp = new ArrayList<>();
    static List<String> result = new ArrayList<>();
    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());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < C; i++) {
            String ap = st.nextToken();
            if(vows.contains(ap))
                vow.add(ap);
            else
                con.add(ap);
        }

        for(int i = 1; i <= L-2; i++) {
            vowDfs(i, 0, 0);
        }

        Collections.sort(result);
        for(int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }

    public static void vowDfs(int depth, int index, int cnt) {
        if(cnt == depth) {
            conDfs(L-depth, 0, 0);
            return;
        }
        for(int i = index; i < vow.size(); i++) {
            temp.add(vow.get(i));
            vowDfs(depth, i+1, cnt+1);
            temp.remove(vow.get(i));
        }
    }

    public static void conDfs(int depth, int index, int cnt) {
        if(cnt == depth) {
            Collections.sort(temp);
            String str = String.join("", temp);
            result.add(str);
            return;
        }
        for(int i = index; i < con.size(); i++) {
            temp.add(con.get(i));
            conDfs(depth, i+1, cnt+1);
            temp.remove(con.get(i));
        }
    }
}

댓글남기기

참고