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

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

---

[접근 방법]

DFS를 사용하여 해결하였다.

<N과 M 시리즈>와 유사한 방법으로 해결하였다.

 

'가능성 있는 암호'는 문자가 '오름차순'으로 나열된 문자열이다.

따라서, dfs함수는 이전 문자의 정보를 가지고 있어야 하기 때문에, 매개변수로 int at을 갖는다.

 

예외로 처리해야 할 사항이 존재한다.

"암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성된다."

 

boolean 자료형을 반환하는 "check" 함수를 생성하여, 위 사항을 예외로 처리 해준다.

 

코드는 아래와 같다.

---

[JAVA 코드]

// 1759번 - 암호 만들기
import java.util.*;
import java.io.*;

public class Main {

    static int L, C;
    static char[] al; // c개의 문자
    static char[] arr; 
    static boolean[] visit;

    static StringBuilder sb; // 출력을 위한 문자열 생성

    // 모음을 최소 1개 포함해야 한다.
    // 자음을 최소 2개 포함해야 한다.
    public static boolean check(char[] a){
        int countV = 0; // vowel : 모음
        int countC = 0; // consonant : 자음

        for(char i : a){
            if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u'){
                countV ++;
            } else {
                countC ++;
            }
        }

        if (countV < 1 || countC < 2){
            return false;
        }
        else {
            return true;
        }
    }

    public static void dfs(int at, int depth){
        if(depth == L){
            if (check(arr)){
                for(char ch : arr){
                    sb.append(ch);
                }sb.append("\n");
            }

            return;
        }

        for(int i=at; i<C; i++){
            
            if (!visit[i]){
                visit[i] = true;
                arr[depth] = al[i];
                dfs(i, depth + 1);
                visit[i] = false;
            }
        }

        return;
    }

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        al = new char[C];
        arr = new char[L];
        visit = new boolean[C];

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

        // 1. 배열 정렬 및 dfs 실행
        sb = new StringBuilder();
        Arrays.sort(al);
        dfs(0, 0);

        // 2. 출력
        bw.write(sb.toString());

        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

1. 어려웠던 점

- 예외적으로 처리 해주어야 할 조건을 곧바로 반영하지 못하였다.

 

2. 알게된 점

- 한 줄에 공백으로 구분되어 주어진 문자들을 char 자료형의 형태로 입력 받는 방법을 알게 되었다.

al = st.nextToken().charAt(0);

 

3. 개선 방향

- 응용 문제를 반복하여 풀어서 숙달해야 함.