[JAVA]백준 1759번: 암호 만들기

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

1759번: 암호 만들기

1. 문제 설명

 

글자 수와 암호의 길이가 주어진다. 주어진 글자를 이용하여 암호를 만드는데, 암호는 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열 되었을 것이라고 추측한다. 암호는 최소 한개의 모음과 최소 두개의 자음으로 구성되어야 한다.

 

2. 풀이

 

백트래킹으로 풀 수 있는 문제이다.

 

암호는 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되기 때문에 암호의 X번째 알파벳은 이전 암호의 알파벳들보다 커야 한다. 

 

따라서 무조건 정렬을 해야된다..!!..

 

기존에 선택한 알파벳보다 큰 알파벳을 선택해나가며 암호의 길이 C만큼의 암호를 만든 후, 그 암호가 최소 한개의 모음과 최소 두개의 자음으로 구성되었는지 확인해야 한다.

 

최소 한개의 모음과 최소 두개의 자음으로 구성되었다면 출력하면 된다.

 

* 로직

- 입력받은 문자들을 정렬한다.

- 기존에 선택한 알파벳보다 큰 알파벳을 하나씩 선택해나가면서 암호를 만들어 간다.

- 암호를 다 만들었다면, 암호가 최소 한개의 모음과 두개의 자음으로 구성되었는지 확인 후, 그렇게 구성되어 있다면 출력

 

 

3. 코드

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

public class Main {

    public static int L, C;
    public static char[] list;
    public static char[] code;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        list = new char[C];
        code = new char[L];

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < C; x++) {
            list[x] = st.nextToken().charAt(0);
        }


        // 정렬
        Arrays.sort(list);

        makeCode(0,0);

    }

    public static void makeCode(int x,int idx) {


        if (idx == L) {
            // 최소 한개의 모음, 최소 2개의 자음인지 확인
            if (isValid()) {
                System.out.println(code);
            }
            return;
        }

        // 아직 길이 L의 코드를 만들지 않았고 글자도 아직 남았다.

        for (int i = x; i < C; i++) {
            code[idx] = list[i];
            makeCode(i+1, idx + 1);
        }
    }

    // 최소 모음 1개, 최소 자음 2개인지 확인
    public static boolean isValid() {
        int mo = 0;
        int ja = 0;

        for (char x : code) {
            if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
                mo++;
            } else {
                ja++;
            }
        }

        if (mo >= 1 && ja >= 2) {
            return true;
        }
        return false;
    }

}