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

문제

BOJ 1759 : 암호 만들기 - https://www.acmicpc.net/problem/1759

풀이

C개 중에 L개를 뽑아 만드는 문자열 중에서 1) 사전순이고 2) 모음(a, e, i, o, u) 1개 이상, 자음 2개 이상 조건을 가지는 문자열 리스트를 출력하는 게 문제이다.

dfs를 사용해서 조합을 구현했다. 배열은 총 3개를 만들었는데,
1. 입력받은 문자들을 저장하는 char[] chars
2. 방문 여부를 체크하는 boolean[] visited
3. 뽑힌 문자들이 담길 char[] selected 이렇게 세 가지 이다.

dfs를 탐색하면서는 문자를 이미 선택했는지 여부와 바로 앞 문자보다 사전적으로 순서가 맞는지를 확인했다.

L개의 문자가 선택되었을 경우 2번 조건이 맞는지 확인했다. 입력값의 범위 (3 ≤ L ≤ C ≤ 15)가 크지 않아서 이중 for문을 사용해서 모음의 개수를 찾고, L-(모음의 개수)==자음의 개수 로 가능한 문자열인지 판단했다.

이후 가능한 문자열에 대해 사전순으로 출력해야 했기 때문에 ArrayList를 sort해서 출력했다.

코드

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

public class Main {
    static char[] chars;
    static char[] selected;
    static boolean[] visited;
    static int L;
    static int C;
    static ArrayList<String> arr;

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

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

        selected = new char[L];
        chars = new char[C];
        for (int i = 0; i < C; i++) {
            chars[i] = st.nextToken().charAt(0);
        }

        visited = new boolean[C];
        arr = new ArrayList<>();
        dfs(0);

        Collections.sort(arr);

        for (String code : arr) {
            System.out.println(code);
        }
    }

    static public void dfs(int count){
        if (count == L) {
            if(checkPossible()){
                arr.add(new String(selected));
            }
            return;
        }
        for (int i = 0; i < C; i++) {
            if (!visited[i]) {
                if(count==0 || selected[count-1]<chars[i]){
                    selected[count] = chars[i];
                    visited[i] = true;
                    dfs(count + 1);
                    visited[i] = false;
                }
            }
        }
    }

    static public boolean checkPossible() {
        // 모음 1개, 자음 2개 이상 있는지 확인
        char[] vowel = {'a', 'e', 'i', 'o', 'u'};
        int cnt_vowel = 0;
        for (char c : selected) {
            for (char v : vowel) {
                if(c==v) {
                    cnt_vowel++;
                }
            }
        }
        if(cnt_vowel==0) return false;

        return (L - cnt_vowel) >= 2;
    }
}

정리

✔ 알고리즘 분류 - 수학, 문자열, 브루트포스, 조합론, 백트래킹
✔ 난이도 - 🟡 Gold 5

🤦‍♀️ 오늘의 삽질리스트

• 모음 1개 자음 2개 조건은 괜히 준게 아니다. 잠깐 생각을 잘못해서 L의 최솟값이 3인데 문자 3개중에 모음이 1개 있으면 자음이 당연히 2개 이상이겠지! 라는 이상한 논리로 모음이 있는지 여부만 체크했다. 3개중에 모음이 1개 이상이라는 것은 1개도 되고 2개도 되고 3개도 된다는 것. 그러면 자음은 2개 이상이라는 조건을 만족하지 않을 수도 있다. 전체 문자 개수 - 모음 개수로 자음의 개수까지 확인해주어야 했다.

• DFS()에서 if (count == L) 부분의 L을 문제 예제로 주어진 4라고 하드코딩을 해놔서,,, (할많하않)

• 그리고 ArrayList 소팅하는거 맨날 까먹는다. 적어놔야지

Collections.sort(arr); // 오름차순
Collections.sort(arr, Collections.reverseOrder()); // 내림차순

참고 사이트

딱히 없음