이번에 풀어본 문제는
백준 1759번 암호 만들기 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int L,C;
    static PriorityQueue<String> answer;
    static List<Character> v; // 모음
    static List<Character> c; // 자음
    static int v_size, c_size;
    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());

        answer = new PriorityQueue<>();
        v = new ArrayList<>();
        c = new ArrayList<>();

        String [] tmp_arr = br.readLine().split(" ");
        for(int i = 0; i < C; ++i)
        {
            char ch = tmp_arr[i].charAt(0);
            if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') v.add(ch);
            else c.add(ch);
        }

        v_size = v.size();
        c_size = c.size();

        Collections.sort(v);
        Collections.sort(c);

        for(int i = 0 ; i < v_size; ++i)
        {
            char next = v.get(i);
            find(next+"",1,1,0,next,i+1,0);
        }
        for(int i = 0; i < c_size; ++i)
        {
            char next = c.get(i);
            find(next+"",1,0,1,next,0,i+1);
        }

        while(!answer.isEmpty()) System.out.println(answer.poll());
        
    }
    static void find(String str,int len,int v_cnt, int c_cnt,char last,int v_idx,int c_idx)
    {
        if(len == L)
        {
            if(c_cnt > 1 && v_cnt > 0) answer.add(str);
            return;
        }
        if(v_idx < v_size)
        {
            for(int i = v_idx; i < v_size; ++i)
            {
                char next_v = v.get(i);

                if(last < next_v) find(str+next_v,len+1,v_cnt+1,c_cnt,next_v,v_idx+1,c_idx);
            }
        }
        if(c_idx < c_size)
        {
            for(int i = c_idx; i < c_size; ++i)
            {
                char next_c = c.get(i);

                if(last < next_c) find(str+next_c,len+1,v_cnt,c_cnt+1,next_c,v_idx,c_idx+1);
            }
        }
    }
}

📝 풀이

L길이의 암호를 C개의 입력받은 알파벳으로 만드는 문제입니다.
조건에 맞는 암호들을 모두 출력합니다.
먼저 자음과 모음을 구분하기 위해 두개의 List를 사용했습니다. 두 리스트는 정렬하여 작은 인덱스부터 오름차순으로 정렬된 상태를 갖습니다.
모든 경우의 수를 고려하려면 하나의 알파벳을 시작점으로 두었을 때, 모음을 뽑거나 자음을 뽑거나 둘중 하나의 경우 이므로 자신보다 높은 인덱스에 위치한 글자 중 값이 큰 알파벳들을 붙여가며 DFS를 진행해줍니다.
마지막으로 우선순위큐에 담긴 정렬된 암호들을 출력해주면 해결됩니다.

📜 후기

최근 구현문제만 풀었어서 오랜만에 신선한 느낌이었습니다 ㅋㅋㅋ
난이도는 적당했다고 생각합니다!