[자바로 푸는 백준] 1759번 암호 만들기

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

1759번: 암호 만들기

✅ 골드 Ⅴ

 

🔶 풀이

최소 한 개의 모음과 두 개의 자음으로 구성된 길이 L의 암호를 출력하라.

 

백트래킹으로 풀어야 된다.

해당 문제에서는 알파벳이 증가하는 순서로 배열되었을 것이라고 한다.

정렬은 필수다.

 

우선, 이미 선택한 알파벳보다 큰 알파벳을 선택해서 임의의 L 길이를 가진 암호를 만든다.

L 길이가 완성됐다면 최소 모음 1개, 자음 2개를 가지고 있는지 판단해 준다.

public static void makeWord(int curIdx, int idx) {
		
    // 자릿수 L까지 채움
    if (idx == L) {
			
        // 최소 모음 1개, 자음 2개 이상인지 확인
        if (canCheck(word)) {
            System.out.println(word);
        }
        return;
    }
		
    // 자릿수 L까지 채우기
    for (int i=curIdx; i<C; i++) {
        word[idx] = wList[i];
        makeWord(i+1, idx+1);
    }
}

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int L, C;
    static char[] wList, word;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        L = Integer.parseInt(st.nextToken()); // 암호의 길이
        C = Integer.parseInt(st.nextToken()); // 조교들이 암호로 사용했을 법한 문자의 개수
		
        word = new char[L];  // 암호
        wList = new char[C]; // 문자의 개수
		
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<C; i++) {
            wList[i] = st.nextToken().charAt(0);
        }
		
        // 정렬
        Arrays.sort(wList);
        makeWord(0, 0);
    }
	
    public static void makeWord(int curIdx, int idx) {
		
        // 자릿수 L까지 채움
        if (idx == L) {
			
            // 최소 모음 1개, 자음 2개 이상인지 확인
            if (canCheck(word)) {
                System.out.println(word);
            }
            return;
        }
		
        // 자릿수 L까지 채우기
        for (int i=curIdx; i<C; i++) {
            word[idx] = wList[i];
            makeWord(i+1, idx+1);
        }
    }
	
    public static boolean canCheck(char[] word) {
        int vowel = 0;     // 모음
        int consonant = 0; // 자음
		
        for (char c : word) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vowel++;
            } else {
                consonant++;
            }
        }
		
        if (vowel >= 1 && consonant >= 2) return true;		
        return false;
    }
}