[BOJ/Java] 1759. 암호 만들기

[BOJ/Java] 1759. 암호 만들기

1759번: 암호 만들기

---

문제 해석

이 문제는 주어진 문자들 중에서 L개를 선택해 가능한 암호를 만드는 문제다. 암호는 최소 한 개의 모음과 두 개의 자음으로 구성되어야 하며, 알파벳 순서대로 배열되어야 한다.

풀이 과정

1. 입력으로 주어진 문자들을 모음과 자음으로 분류한다.
2. 가능한 모든 모음과 자음의 조합을 찾아서 암호를 생성한다. 이때, 모음은 최소 1개에서 최대 L-2개 사이, 자음은 최소 2개에서 최대 L-1개 사이여야 한다.
3. 모음과 자음의 선택은 백트래킹을 사용해 모든 가능한 조합을 시도한다.
4. 각 조합을 기반으로 완성된 암호를 생성한 후, 정렬하여 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No1759;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private int L;  // 암호 길이
    private int C;  // 사용할 수 있는 문자 수
    private List<Character> consonants;  // 자음 리스트
    private List<Character> vowels;  // 모음 리스트
    private int[] conSel;  // 자음 선택 배열
    private StringBuilder sb = new StringBuilder();  // 결과 문자열
    private int[] vowSel;  // 모음 선택 배열
    ArrayList<String> resList = new ArrayList<>();  // 결과 저장 리스트

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        consonants = new ArrayList<>();
        vowels = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            char c = st.nextToken().charAt(0);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vowels.add(c);  // 모음 추가
            } else {
                consonants.add(c);  // 자음 추가
            }
        }

        sol();  // 암호 생성 솔루션 실행

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

    private void sol() {
        consonants.sort((o1, o2) -> o1 - o2);
        vowels.sort((o1, o2) -> o1 - o2);
        for (int i = 2; i <= L - 1; i++) {
            conSel = new int[i];
            vowSel = new int[L-i];
            consonantsPermutation(0, 0);  // 자음에 대한 순열 생성
        }
        resList.sort((o1, o2) -> o1.compareTo(o2));  // 결과 정렬
        for (String res: resList) {
            sb.append(res).append("\n");
        }
    }

    private void consonantsPermutation(int k, int v) {
        if (k == conSel.length) {
            vowelsPermutation(0, 0);
            return;
        }

        for (int i = 0; i < consonants.size(); i++) {
            if ((v & (1 << i)) == 0) {
                conSel[k] = i;
                consonantsPermutation(k + 1, v | (1 << i));  // 다음 자음 선택
            }
        }
    }

    private void vowelsPermutation(int k, int v) {
        if (k == vowSel.length) {
            makePassword();  // 암호 생성
            return;
        }

        for (int i = 0; i < vowels.size(); i++) {
            if ((v & (1 << i)) == 0) {
                vowSel[k] = i;
                vowelsPermutation(k + 1, v | (1 << i));  // 다음 모음 선택
            }
        }
    }

    private void makePassword() {
        char[] res = new char[L];
        int idx1 = 0, idx2 = 0;
        for (int i = 0; i < L; i++) {
            if(idx1 == vowSel.length) {
                res[i] = consonants.get(conSel[idx2++]);
            } else if(idx2 == conSel.length){
                res[i] = vowels.get(vowSel[idx1++]);
            } else {
                res[i] = vowels.get(vowSel[idx1]) < consonants.get(conSel[idx2]) ? vowels.get(vowSel[idx1++]) : consonants.get(conSel[idx2++]);
            }
        }
        resList.add(String.valueOf(res));
    }
}

시간 복잡도 분석

이 알고리즘은 모음과 자음의 모든 가능한 조합을 고려하여 암호를 생성한다. 최악의 경우, C개 중 L개를 선택하는 조합의 수에 비례하여 시간 복잡도가 결정된다. 조합의 계산 복잡도는 O(C^L)로 예상할 수 있다.

느낀점

이 문제는 조합과 순열을 사용하여 주어진 조건에 맞는 암호를 생성하는 문제로, 백트래킹을 사용하여 모음과 자음의 조합을 효율적으로 탐색하는 방법을 잘 이해하고 구현하는 것이 중요하다.