[BaekJoon] 1759번 암호 만들기 (Java) 문제 풀이 [Gold 5]

문제

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

1759번: 암호 만들기

 

어떻게 풀 것인가?

문제를 처음 봤을 때 우선적으로 백트레킹을 이용한 순열과 조합을 떠올렸다. 하지만 중요한 한 부분을 놓쳐서 계속 문제를 틀렸는데, 이는 문제에서 "암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다." 라는 부분을 놓쳤다. 이에 그래서 모음의 갯수를 카운트하는 로직을 구성하여 문제를 풀었다. 그 외에는 combination 알고리즘 과 동일하다.

 

풀면서 놓쳤던점

문제를 꼼꼼히 읽지 않았다.

 

이 문제를 통해 얻어갈 것

순열과 조합 알고리즘을 응용하였다.

 

내 코드 

import java.util.*;

public class Main {

    static char[] arr;
    static boolean[] visited;
    static int l, c;

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

        arr = new char[c];
        visited = new boolean[c];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.next().charAt(0);
        }
        Arrays.sort(arr);

        combination(0, 0);

    }

    static void combination(int start, int count) {
        if (count == l) {
            StringBuilder word = new StringBuilder();
            int a = 0;
            int b = 0;
            for (int i = 0; i < c; i++) {
                if (visited[i]) {
                    word.append(arr[i]);
                    if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u') {
                        a++;
                    } else {
                        b++;
                    }
                }
            }
            if (a >= 1 && b >= 2) {
                System.out.println(word);
            }
        }

        for (int i = start; i < c; i++) {
            visited[i] = true;
            combination(i + 1, count + 1);
            visited[i] = false;
        }
    }
}

 

참고

X