[백준] 1759번_암호 만들기_Java

문제 링크 👉🏻 https://www.acmicpc.net/problem/1759

👀 문제 접근

---

한 개 이상의 모음, 두 개 이상의 자음이 포함된 암호 만들기

C 개의 알파벳들이 주어졌을 때, 이 중 L 개의 알파벳을 조합하여 암호를 만든다.

암호에는 최소 한 개의 모음과 최소 두 개의 자음으로 구성돼야 한다. 또한 알파벳은 사전순 기준으로 증가하는 순으로 배열돼야 한다.

🔎 해결 방식

---

입력과 저장

• L , C , C 개의 문자 배열 alphabets 를 입력받는다.
• 알파벳은 증가하는 순으로 배열돼야 하기 때문에 alphabets 는 정렬을 하도록 한다.

암호 만들기

• 백트레킹을 통해 암호 조합을 해나가야 하므로 dfs 함수를 만든다
  • 조합한 암호를 저장할 문자 배열을 저장할 password , 이미 조합에 포함 시킨 문자열을 저장할 visited 집합, 조합된 크기 depth 와 순회를 시작할 정수를 저장할 start 를 파라미터로 선언한다.
• depth 와 L 이 같아졌을 때 적합한 비밀번호일 때 조합된 비밀번호를 출력한다.
  • 비밀번호 적합성 검사
    1. 조합된 문자열을 저장한 visited 집합을 깊은 복사한 후, 해당 집합에서 모음만 제거한다.
    2. 자음만 남은 집합의 크기가 2 이상이고, 조합된 문자열을 저장한 집합 크기에서 자음만 남은 집합 크기를 뺐을 때 0이 아니면 true 를 리턴한다.
• 조합 가능한 문자열을 순회하여 암호를 만든다
  1. 암호는 중복될 수 없으므로 순회 시작을 start 로 하여 다음 함수를 호출할 때 현재 i 에서 1 더하여 호출할 수 있도록 한다.
  2. 현재 alphabets[i] 를 방문하지 않았을 때 visited 집합에 더하고, password[depth] 를 alphabets[i] 로 저장한다.
  3. depth 와 i 에 각각 1 더하여 dfs 함수를 호출한다.
  4. 함수가 리턴되면 alphabets[i] 를 visited 집합에서 제거한다.

💻 구현 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static int l;
    static int c;
    static char[] alphabets;
    static final Set<Character> vowel = Set.of('a', 'e', 'i', 'o', 'u');

    public static boolean isProperPW(Set<Character> visited) {
        HashSet<Character> consonant = new HashSet<>(visited);
        consonant.removeAll(vowel);

        if (consonant.size() >= 2 && visited.size() - consonant.size() != 0) return true;
        return false;
    }

    public static void dfs(char[] password, Set<Character> visited, int depth, int start) {
        if (depth == l) {
            if (isProperPW(visited)) {
                for (char pw : password) {
                    System.out.print(pw);
                }
                System.out.println();
            }
            return;
        }

        for (int i = start; i < c; i++) {
            if (!visited.contains(alphabets[i])) {
                visited.add(alphabets[i]);
                password[depth] = alphabets[i];

                dfs(password, visited, depth + 1, i + 1);

                visited.remove(alphabets[i]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        l = Integer.parseInt(input[0]);
        c = Integer.parseInt(input[1]);
        alphabets = Arrays.stream(br.readLine().split(" "))
                .map(s -> s.charAt(0))
                .collect(StringBuilder::new,
                        StringBuilder::append,
                        StringBuilder::append)
                .toString()
                .toCharArray();

        Arrays.sort(alphabets);

        dfs(new char[l], new HashSet<>(), 0, 0);
    }
}

✨ 마무리

골드 문제인거 치고는 깊이 고민하지 않아도 쉽게 풀 수 있었다. 다만, 문제를 제대로 보지 않아 시행착오를 몇 번 겪었다.

첫 시행 착오는 모음 포함 조건을 boolean 변수를 선언하여 dfs 함수 호출 전에 현재 알파벳이 모음이면 true로 저장하도록 한 것이다. 이렇게 하니, 이미 true로 저장해버린 변수라 백트래킹 하는 의미 없이, 모음이 포함되지 않은 암호 조합이 나오기도 했다. 그걸 해결하기 위해 함수가 리턴됐을 때 다시 한번 모음 여부를 체크하여 false로 업데이트 되도록 했는데, 이렇게 하니 모음이 포함된 문자열도 출력되지 않는 오류가 있었다. 그렇게 시행착오를 겪은 후에 생각해낸 게 depth가 l과 일치했을 때 모음 포함 여부를 검증하는 것이었다.
또 문제를 제대로 읽지 않아 모음만 무조건 포함되는 조건만 만족시킨 채로 제출해서 틀리고, 적합한 암호인지 검사할 때 얕은 복사한 채로 removeAll해버려서 번번이 실패하는 실수가 있었다.

답을 찾아내는데 길을 많이 돌아가긴 했지만, 그래도 그 실패에 대한 해결책을 찾아내는데 그리 오랜 시간이 걸리지 않았다. 조금만 생각해보면 금방 풀어낼 수 있는 난이도의 문제였다.