백준 1759번 : 암호 만들기 자바

🧫 문제 분석

 

✔️ 출처

암호 만들기 골드 5

 

📖 문제

 

 

조건

최소 한개의 모음 && 두 개 이상의 자음 

알파벳이 사전 순서대로 정렬   ex) ba 불가능, ab 가능

 

 

알파벳을 배열에 담고 오름차순 정렬한 다음

 

길이를 주고 각 자리수에 맞게 완전탐색을 해본다. 

처음(0일때) a일 경우 a를 방문했다고 하고 나머지 c i t s w 에 대해서 또 DFS를 한다.

 

중요한 것은 이전 사전 순이기에 이전 알파벳보다 현재 알파벳이 커야한다.(순서로 따지자면 뒷 번호여야 한다.)

따라서 이전 알파벳에 대한 인덱스를 매개변수로 넘긴다. 

 

 그리고 모음의 만들어야하는 암호의 길이 L - 모음의 개수 = 자음의 개수이다.

 

 

 

 

---

🔅 문제 풀이

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 String vowel = "aeiou";
    static String[] keyword;
    static String[] password;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    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());
        keyword = new String[C];
        password = new String[L];
        visited = new boolean[C];
        
        for (int i = 0; i < C; i++) {
            keyword[i] = st.nextToken();
        }
        
        Arrays.sort(keyword);
        dfs(0, -1);
        
        System.out.println(sb.toString());
    }


    private static void dfs(int depth, int pre) {
        if (depth == L) {
            if (validVowel()) return;

            // 이상없다면 정상 진행
            for (String ps : password) {
                sb.append(ps);
            }
            sb.append("\n");
            return;
        }


        for (int i = 0; i < C; i++) {
            if (!visited[i] && pre < i) {
                visited[i] = true;
                password[depth] = keyword[i];
                dfs(depth + 1, i);
                visited[i] = false;
            }
        }


    }

	// 모음 검증
    private static boolean validVowel() {
        int vowCount = 0;
        for (String s : password) {
            // 검증
            vowCount += vowel.contains(s) ? 1 : 0;

        }
        // 전체길이 - 모음의 개수 = 자음의 개수
        if(L - vowCount < 2 || vowCount == 0) {
            return true;
        }
        return false;
    }


}

 

---

 

 

 

❗ 오답노트 / 필요한 지식

1. 백트래킹, 완전탐색 매우 취약한 부분이므로 많이 풀어볼 예정이다.