백준 온라인 저지 1759번 암호 만들기

문제 출처 : https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

---

 

풀이과정

 

문제의 입력범위가 작으므로 완전탐색 방법으로 해결할 수 있다.

1. DFS로 가능한 모든 경우의 수를 만들고 검증 메소드를 사용해서 최소 한 개 이상의 모음과 최소 두 개 이상의 자음을 가진 문자열만 출력하도록 구현했다.
2. 문제에서 알파벳이 암호에서 증가하는 순서로 배열된다고 했으므로 입력받은 알파벳을 사전 순으로 정렬 후 경우의 수를 만들면 별도로 순서를 검사할 필요가 없다.

 

---

 

소스코드

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

public class Main {
    static int L, C;
    static char[] alpha;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
        L = Integer.parseInt(stringTokenizer.nextToken());
        C = Integer.parseInt(stringTokenizer.nextToken());
        alpha = new char[C];
        stringTokenizer = new StringTokenizer(reader.readLine());

        for (int i = 0; i < C; i++) {
            alpha[i] = stringTokenizer.nextToken().charAt(0);
        }
        Arrays.sort(alpha);

        for (int i = 0; i <= C - L; i++) {
            dfs(i, 1, ""+ alpha[i]);
        }
    }

    private static boolean validation(String s) {
        int jaCount = 0; //자음
        int moCount = 0; //모음
        for(int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if(c == 'a' || c == 'e' || c == 'i' || c =='o' || c=='u')
                moCount++;
            else jaCount++;
        }

        return moCount >= 1 && jaCount >=2;
    }

    private static void dfs(int index, int count, String s) {
        if(count == L) {
            if(validation(s)) {
                System.out.println(s);
            }
            return;
        }

        for(int i=index+1;i<C;i++) {
           dfs(i, count + 1, s + alpha[i]);
        }

    }
}