[백준] 1759 암호 만들기(Gold.5) - 백트래킹(Backtracking)

문제

• 암호는 서로 다른 L개의 소문자로 이루어져 있고 최소 한 개의 모음, 두 개의 자음으로 이루어져 있다.
  • 암호는 오름차순(사전 순)으로 정렬되어 있다.
  • 문자의 종류는 C개이다.
  • 즉, 암호는 L개의 서로 다른 소문자이고 이때 사용할 수 있는 문자의 종류는 C개이다.

코드

전형적인 백트래킹을 이용하여 조합하는 문제였다. 조건 두 개를 처리하는 데 시간이 오래 걸렸다.

막상 풀고 보니 별 거 아니어서 당황 ;;

1. 입력 받은 알파벳을 사전 순서로 정렬한다.
2. 백트래킹을 이용하여 단어를 조합한다.
   • 조건에 해당한다면 result배열에 삽입한다.
     • 단어가 L자리
     • 모음 1개 이상, 자음 2개 이상
3. result 배열에 있는 값들을 출력한다.

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

public class _1759 {
    static ArrayList<String> result = new ArrayList<>();
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        // GPT 참고
        char[] words = br.readLine().replaceAll(" ", "").toCharArray();

        Arrays.sort(words);

        // 단어 조합
        for (int i = 0; i < words.length; i++) {
            backtracking("", words, i, L);
        }

        for (String rs : result) {
            System.out.println(rs);
        }


    }

    public static void backtracking(String nowWord, char[] word, int idx, int L) {
        String newWord = nowWord + word[idx];

        if (newWord.length() == L && vowelCheck(newWord)) {
            result.add(newWord);
            return;
        }

        for (int i = idx+1; i < word.length; i++) {
            backtracking(newWord, word, i, L);
        }

    }

    // 모음 한 개 이상, 자음 두 개 이상 체크
    public static boolean vowelCheck(String newWord) {
        String[] vowels = {"a", "e", "i", "o", "u"};
        int vowelCnt = 0;
        for (String vowel : vowels) {
            if (newWord.contains(vowel))
                vowelCnt++;
        }
        if (vowelCnt >= 1 && newWord.length() - vowelCnt >= 2) {
            return true;
        } else {
            return false;
        }
    }
}

 

정답이긴 한데 시간이 좀 아쉬워서 코드를 살짝 고쳐봤다.

System.out.println()을

for (String rs : result) {
            System.out.println(rs);
        }

BufferedWriter로 바꾸니

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (String rs : result) {
            bw.write(rs);
            bw.newLine();
        }
        bw.flush();
        bw.close();

 

짠~

180ms에서 168ms로 줄어들었다!!😎 

사실 별 의미는 없지만 이렇게라도 줄이고 싶었어..