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

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

 

⭐️ 중요 포인트

1. 기본적인 백트리킹과 동일하나 자음과 모음의 개수를 카운트할 수 있는 메서드가 필요하다. (처음에는 모음의 개수만 세고 자음은 최소 두 개라는 조건을 만족하지 않아 틀렸었다.)

2. 중복되는 것은 없으며 오름차순으로 정렬된 결과값을 출력해야하기 때문에 사용할 수 있는 알파벳을 오름차순 정렬시켜 초기값을 세팅한다.

3. 현재 코드에서 처음에 ArrayList.contains()를 통해 모음이 최소 한 개를 만족하는지 판단했었는데. 모음의 개수가 5개이고, N이 크다면 모음이 존재하는지 판단하는 메서드의 시간복잡도는 O(5N)이 된다. 현재 코드는 contains()가 빠지고 O(N)으로 리스트 전체를 순회하며 카운트하기 때문에 필요없지만, 만약 이후에 contians()가 반복적으로 필요한 문제가 나올 경우에는 HashMap을 통해 값을 저장하고 해당 값이 있는지 확인하려면 HashMap.contains()를 사용하면 O(1)에 확인이 가능하다.

 

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

public class P1759 {

    static BufferedReader br;
    static BufferedWriter bw;

    static int L;
    static int C;
    static List<Character> alphabets;
    static List<Character> selected;


    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        alphabets = new ArrayList<>();
        selected = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            alphabets.add(st.nextToken().charAt(0));
        }

        Collections.sort(alphabets);
    }

    static void solve() throws IOException {

        recursion(0);


    }

    static void recursion(int idx) throws IOException {
        if (selected.size() == L) {
            int vowelCount = countVowel();
            int consonantCount = selected.size() - vowelCount;
            if (vowelCount >= 1 && consonantCount >= 2) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < selected.size(); i++) {
                    sb.append(selected.get(i));
                }
                bw.write(sb.toString());
                bw.newLine();
            }
            return;
        }

        for (int i = idx; i < alphabets.size(); i++) {
            selected.add(alphabets.get(i));
            recursion(i + 1);
            selected.remove(selected.size() - 1);
        }

    }

    static int countVowel() throws IOException {
        int ret = 0;
        for (int i = 0; i < selected.size(); i++) {
            if (selected.get(i) == 'a' || selected.get(i) == 'e' || selected.get(i) == 'i' || selected.get(i) == 'o' || selected.get(i) == 'u') {
                ret++;
            }
        }

        return ret;
    }

    public static void main(String[] args) throws IOException {
        init();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

}