[JAVA] 백준 알고리즘 1759번 (암호 만들기)

문제

---

이번에 다뤄볼 문제는 1759번 문제 '암호 만들기'입니다.

 

우선 문제를 분석해보도록 하겠습니다.

문제에서 원하는건 "주어진 문자들을 활용하여 L개의 문자로 구성된 암호문자열을 만들어내라" 입니다.

첫째 줄에서 두 정수를 입력받습니다. L = 암호문자의 글자수, C = 암호를 구성할 문자들의 수

두번째 줄에서는 C개 만큼의 암호구성이 주어지네요.

그리고 여기서 조건이 두가지가 주어졌습니다.

1. 최소 한 개의 모음, 최소 두 개의 자음 으로 구성된 암호여야 한다.

2. 각 알파벳 암호는 오름차순을 갖는다.

 

두번째 조건의 경우 Arrays.sort() 메서드를 통해 입력받은 C개의 암호문자를 미리 정렬을 시켜놓고 진행하면 쉽게 만족시킬 수 있으니 첫번째 조건에 대해서만 메서드를 하나 만들어 체크하면 되겠습니다.

 

그럼 이제 아래의 코드를 보겠습니다.

입력을 다 받은 후 createPasswords 메서드를 호출합니다.

이때 함수 안에서 재귀를 돌 것이기에 인덱스 2개를 받고 암호를 담을 String 파라미터(pwd)를 하나 받습니다.

해당 함수 안에서 매번 반복할때 조건에 부합하는 암호가 존재하는지 체크하고 부합한다면 StringBuilder에 append 해둡니다. 암호 문자의 개수에 만족하고 최소 1개 이상의 모음, 최소 2개 이상의 자음을 갖는다면 암호 조건에 부합합니다.

자음과 모음에 대한 조건에 만족하는지 알기 위하여 암호를 파라미터로 받는 validatePassword 메서드를 만들었습니다.

미리 정의해둔 모음배열(vowels)을 순회하며 암호가 해당 모음을 갖고있는지 체크합니다. 만약 있다면 최소 1개 이상의 모음 조건은 달성하였고 해당 문자를 암호에서 지웁니다. 그렇게 모음배열을 다 돌고 나왔을땐 암호에 모음이 존재하지 않을 것이고 그 길이가 2 이상이라면 자음 2개 이상을 갖고있다고 판단 할 수 있습니다.

 

마지막으로 StringBuilder에 append해뒀던 암호들을 출력하면 문제를 해결하게 됩니다.

---

코드(JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static String[] vowels = {"a","e","i","o","u"};
    static StringBuilder sb;

    static int l;
    static int c;
    static char[] words;

    public static void main(String[] args) throws IOException {
        sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        words = new char[c];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < c; i++) {
            words[i] = st.nextToken().charAt(0);
        }

        Arrays.sort(words);
        createPasswords(0, 0, "");

        System.out.println(sb);
    }

    private static void createPasswords(int pwdIndex, int startIndex, String pwd) {
        if (pwdIndex == l && validatePassword(pwd)) {
            sb.append(pwd).append("\n");
            return;
        }
        for (int i = startIndex; i < words.length; i++) {
            createPasswords(pwdIndex + 1, i + 1, pwd + Character.toString(words[i]));
        }
    }

    private static boolean validatePassword(String pwd) {
        boolean containsVowel = false;
        for(String vowel : vowels) {
            if(pwd.contains(vowel)) {
                containsVowel = true;
                pwd = pwd.replace(vowel, "");
            }
        }
        return containsVowel && pwd.length() >= 2;
    }

}

 

1759번: 암호 만들기