[백준] 1759번 - 암호 만들기 [Java]

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

 

[백준] 1759번 - 암호 만들기 [Java]

[백준] 1759번 - 암호 만들기 [Java]

---

1.  아이디어

 

조합과 백트래킹으로 간단하게 해결할 수 있다.

---

2. 문제풀이

 

암호는 서로 다른 C개의 알파벳에서 L개를 선택하는 조합인데 한 개 이상의 모음과 두 개 이상의 자음으로 이루어져야한다.

조합을 기본으로 구현을 했는데 파라미터에 자음과 모음의 개수를 들고 다니며 조합이 완성되었을 때 자음과 모음의 개수가 조건에 맞는지 확인하는 방식으로 구현했다.

---

3. 코드

 

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

public class Main {

    private static final StringBuilder sb = new StringBuilder();
    private static final Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

    private static char[] arr;
    private static char[] sel;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        arr = new char[C];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(arr);

        sel = new char[L];

        combination(0, 0, 0, 0);

        bw.write(sb.toString());
        bw.flush();
    }

    private static void combination(int idx, int selIdx, int cntJa, int cntMo) {
        if (selIdx == sel.length) {
            if (cntJa < 2 || cntMo < 1) return;

            for (char c : sel) {
                sb.append(c);
            }
            sb.append("\n");
            return;
        }

        for (int i = idx; i < arr.length; i++) {
            sel[selIdx] = arr[i];
            if (set.contains(arr[i])) {
                combination(i + 1, selIdx + 1, cntJa, cntMo + 1);
            } else {
                combination(i + 1, selIdx + 1, cntJa + 1, cntMo);
            }
        }
    }

}

---

4. 후기