[백준] 1759 암호 만들기 (JAVA)

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

1759번: 암호 만들기

풀이

 이 문제는 기존의 백트래킹문제를 풀어보았다면 쉽게 풀리는 문제였다. 기존의 백트래킹의 문제(N과M문제 시리즈들)들과는 다른점이라면 이번 1759번 암호만들기는 숫자가 아닌 문자가 주어졌다는 것이다. 하지만 그 뿐일뿐 숫자가 문자로 바뀌었다는것을 제외하고서는 전부 동일하다 사전식으로 출력을 한다든지 아니면 어떠한 조건이 있는 점이 말이다. 

 

 알고리즘의 개요는 다음과 같다 우선 입력값으로 L C값을 입력을 받아 C의 크기에 맞게 배열을 생성해준다. 이때 배열은 입력문자들을 저장할 arr과 방문을 체크해놓을 visit로 해놓는다. 입력을 전부 받았더라면 arr를 오른차순으로 정렬해준다. (이 문제는 이렇게 해야만 풀린다) 그후 암호를 만드는 메소드로 이동해 암호가 완성될때 까지 재귀적으로 호출해준다. 그러다 만약 암호가 완성이 되었다면(이때는 자음의 수나 모음의 수를 신경쓰지 않고 중복만들 피해서 암호를 만드는데 집중한다.) 바로 출력을 해주는 메소드로 넘어간다. 그리고 출력을 해주는 메소드에서 자음과 모음의 수를 검사하고 만약 조선에 부합하지 않는다면 출력하지 않고 바로 리턴해준다. 만약 조건에 부합한다면 출력을 해주고 메소드를 끝낸다.

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

    public static int L, C;
    public static String[] arr; //arr 저장하는곳
    public static boolean[] visited; //각 원소의 선택여부를 판단
    public static int num_vow; //모음 수
    public static int num_cons; //자음 수
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    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());

        arr = new String[C];
        visited = new boolean[C];

        st = new StringTokenizer(br.readLine(), " "); // 띄어쓰기 기준으로 자름
        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken();
        }

        Arrays.sort(arr); //정렬

        MakePassWord(0, 0);
        bw.flush();
        bw.close();
    }

    public static void MakePassWord(int depth, int idx) throws IOException {
        if (depth == L) { //만약 전부 선택 되어있다면 출력메소드로 이동
            printArr();
            return;
        }

        for (int i = idx; i < C; i++) {
            if (!visited[i]) {
                visited[i] = true; //미방문이라면 방문값을 true로 해놓고 재귀적으로 호출
                MakePassWord(depth + 1, i + 1);
                visited[i] = false; //방문끝났으면 false로 바꿈
            }
        }
    }

    private static void printArr() throws IOException { //출력
        int i = 0;
        for (String val : arr) { //자음수와 모음수를 계산
            if (visited[i++]) {
                if (val.equals("a") || val.equals("e") || val.equals("i") || val.equals("o") || val.equals("u")) {
                    num_vow++;
                } else num_cons++;
            }
        }

        if (!(num_vow >= 1 && num_cons >= 2)) { // 만약 자음의 수이 두개 이상이 안되거나 모음의 수이 하나 이상이 안될시
            num_vow=0;
            num_cons=0;
            return;
        }

        i = 0;
        for (String val : arr) {
            if (visited[i++])
                bw.write(val);
        }
        bw.write("\n");
        num_cons = 0;
        num_vow = 0;
        return;
    }
}