백트래킹 유형의 문제~_~

문제링크

백준 #1759. 암호 만들기

풀이방법

3 ≤ L ≤ C ≤ 15 조건 때문에 완전탐색으로 해결 할 수 있는 문제라고 판단했다. 이전의 문제들과 달리 백트래킹을 사용했다. 백트래킹은 완전탐색 알고리즘 중 DFS를 사용하면서 가지치기를 통해 비효율적인 경로를 차단하는 알고리즘이다. 모음 최소 1개, 자음 최소 2개라는 조건을 이용해 가지치기를 진행했다.

조건은 다음과 같다.

if ((numOfConsonant >= 1) && (numOfVowel >= 2)) return true;
else if ((numOfConsonant < 1) && (left < 1)) return false;
else if ((numOfVowel < 2) && ((left + numOfVowel) < 2)) return false;
else return true;

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class PasswordMaker {
    static int l;
    static int c;

    static ArrayList<CharInfo> charInfos = new ArrayList<>();
    static StringBuilder result = new StringBuilder();

    static String vowels = "aeiou";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        l = sc.nextInt();
        c = sc.nextInt();
        sc.nextLine();

        String tempInput = sc.nextLine();
        for (int i = 0; i < tempInput.length(); i++) {
            if (tempInput.charAt(i) != ' ') charInfos.add(new CharInfo(tempInput.charAt(i)));
        }
        Collections.sort(charInfos); // 암호는 알파벳 순이기 때문에 미리 정렬

        searchPassword(0, l);
        System.out.print(result.toString());
    }

    static void searchPassword(int start, int left) {
        if (!isPossiblePassword(left)) return; // 모음 최소 1개, 자음 최소 2개라는 조건으로 가지치기 진행
        if (left == 0) {
            result.append(
                    charInfos.stream().
                            filter(charInfo -> charInfo.visited).
                            map(CharInfo::toString).
                            reduce("", String::concat)
            ); // 한 비밀번호가 완성 되었을 때, visited로 비밀번호의 일부인지 판단, String으로 변환
            result.append("\n");

            return;
        }

        for (int i = start; i < c; i++) {
            charInfos.get(i).visited = true;
            searchPassword(i + 1, left - 1);
            charInfos.get(i).visited = false;
        }
    }

    static boolean isPossiblePassword(int left) {
        int numOfConsonant = (int) charInfos.stream().
                filter(charInfo -> (charInfo.visited && (vowels.indexOf(charInfo.alphabet) != -1))).
                count(); // charInfos 중 모음 개수를 카운트
        int numOfVowel = (l - left) - numOfConsonant;

        if ((numOfConsonant >= 1) && (numOfVowel >= 2)) return true;
        else if ((numOfConsonant < 1) && (left < 1)) return false;
        else if ((numOfVowel < 2) && ((left + numOfVowel) < 2)) return false;
        else return true;
    }
}

class CharInfo implements Comparable<CharInfo> {
    public char alphabet;
    public boolean visited;

    public CharInfo(char alphabet) {
        this.alphabet = alphabet;
        visited = false;
    }

    @Override
    public String toString() { // stream map 메소드를 통해 CharInfo -> String 변환을 위해 재정의
        return Character.toString(alphabet);
    }

    @Override
    public int compareTo(CharInfo o) { // 알파벳을 오름차순으로 정렬하기 위해 구현
        return alphabet - o.alphabet;
    }
}

🔥🔥🔥