[백준] 1759 암호 만들기(Java)

문제링크

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

문제분석

암호조건

• L개의 서로다른 알파벳 소문자
• 최소 1개의 모음(a, e, i, o, u)
• 최소 2개의 자음
• 오름차순으로 정렬

입력

• 암호의 길이 L
• 암호 후보 개수 C
• 3 ≤ L ≤ C ≤ 15

풀이

1. 입력을 받는다
2. DFS를 통해 조합을 구해나간다.

DFS(int idx, ArrayList<Character> vowel, ArrayList<Character> consonant){
	if(선택된 개수 == L){
    	출력
    }else{
    	조합을 구한다(모음이면 vowel, 자음이면 consonant에 넣는다)
    }
}

• idx : 현재 선택 가능한 index
• vowel : 선택된 모음이 담긴 List
• consonant : 선택된 자음이 담긴 List

시간 복잡도

조합에서 하나의 문자를 선택할지, 말지에 따라 2갈래가 생긴다. 최대 후보 개수 C ≤ 15 이다.
최대 2^15 = 32768 이므로, 제한 시간내에 계산 가능하다.

코드

import java.util.*;

public class Main {
    //모음 리스트
    static char[] vowelList = {'a', 'e', 'i', 'o', 'u'};

    //입력 받을 변수 전역으로 선언
    static int L, C;
    static char[] input;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        //입력 받기
        L = scanner.nextInt();
        C = scanner.nextInt();
        input = new char[C];
        for(int i=0; i<C; i++) input[i] = scanner.next().charAt(0);
        Arrays.sort(input);

        //조합을 구하는 DFS
        DFS(0, new ArrayList<>(), new ArrayList<>());
    }

    static void DFS(int idx, ArrayList<Character> vowel, ArrayList<Character> consonant){
        //암호 개수 충족
        if(vowel.size() + consonant.size()==L) {
            //암호 조건 검사
            if (vowel.size() >= 1 && consonant.size() >= 2) {
                ArrayList<Character> out = new ArrayList<>();
                out.addAll(vowel);
                out.addAll(consonant);
                Collections.sort(out); //출력전 정렬
                for (Character c : out) {
                    System.out.print(c);
                }
                System.out.println();
            }
            return;
        }else {
        	//조합을 구한다.
            for (int i = idx; i < C; i++) {
                if (isVowel(i)) { //모음인 경우
                    vowel.add(input[i]);
                    DFS(i + 1, vowel, consonant);
                    vowel.remove(vowel.size()-1);
                } else { //자음인 경우
                    consonant.add(input[i]);
                    DFS(i + 1, vowel, consonant);
                    consonant.remove(consonant.size() - 1);
                }
            }
        }
    }

    // 해당 idx의 input이 모음인지 확인하는 함수
    private static boolean isVowel(int currentInputIndex) {
        boolean isVowel = false;
        for (char v : vowelList) {
            if (v == input[currentInputIndex]) {
                isVowel = true;
                break;
            }
        }
        return isVowel;
    }
}