[문제 풀이] 백준 1759번 암호 만들기 JAVA

문제

  문제접근 방법   

해당 문제는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어있는 암호를 만드는 문제로 각각의 암호는 오름차순으로 정렬되어있다고 할때 C개의 알파벳이 주어지면 몇개의 암호 경우의 수가 나오는지를 출력하는 문제이다. 여기서 L은 암호의 길이, C는 암호를 만들 수 있게 주어진 알파벳의 개수이다.

처음 문제를 읽고 조건과 중요한 부분을 따로 적어두었는데 본 문제에서는 총 3개지 정도를 고려하여 코드를 작성하면 되겠다고 생각했다. 고려 사항은 아래와 같다.

1. 한개 이상의 모음

2. 두개 이상의 자음

3. 오름차순 정렬

위에 작성하였듯이 하나의 암호는 최소 1개의 모음과 2개의 모음이 포함되어야하면 암호가 완성되었을때 오름차순이어야한다는 것이다. 여기서 다른 조건은 다 이해 가지만 오름차순이라고 하면 조금 어렵게 느껴질 수도 있을것이라고 생각한다.

간단하게 예를 들어보면 abc는 가능하지만 bac는 불가능하다는 것이다.

그래서 위의 조건을 고려하면서 어떤 방식으로 접근할까 고민하다가 해당 문제가 순열과 유사하다고 판단 dfs를 활용해 코드를 작성하기로 결정하였고 아래와 같이 초기 코드를 작성하였다.

 

< 초기 코드 1 >

import java.util.*;

public class Main{
    public static List<Character> list=new LinkedList<>();
    public static StringBuilder sb=new StringBuilder();
    public static boolean visited[];
    public static char password[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int l=s.nextInt();
        int c=s.nextInt();
        visited=new boolean[c];
        password=new char[c];
        for(int i=0;i<c;i++){
            list.add(s.next().charAt(0));
        } 
        Collections.sort(list);
        dfs(0,l,0);
        System.out.println(sb);
        
    }
    public static void dfs(int start,int endPoint,int depth){
        if(depth==endPoint){
            for(int i=0;i<password.length;i++){
                sb.append(password[i]);
            }sb.append("\n");
            return;
        }
        
        for(int i=start;i<visited.length;i++){
            if(!visited[i]){
                visited[i]=true;
                if(depth==0){
                    password[depth]=list.get(i);
                    dfs(i,endPoint,depth+1);
                }
                if(depth!=0&&password[depth-1]<list.get(i)){
                    password[depth]=list.get(i);
                    dfs(i,endPoint,depth+1);
                }
                visited[i]=false;
            }
        }
    }
}

초기 코드에서는 위에서 고려해야한다고 했던 부분들중 오르차순 관련만 고려했던 코드이다. 분명 문제를 풀기전에 고려해야할 점을 적어두고 시작했지만 막상 문제에서는 3번 조건에 매몰되어 그 조건만 구현하고 오류를 찾고있었다. 

또 위에서 처럼 반복문에서 i=start와 같이 작성하면 아래처럼 비교하는 조건문은 필요없는데 이또한 오류를 찾으면서 

발견해 수정하였다. 

여기서 3번 조건을 만족하려면 정렬을 해주어여한다. 어차피 dfs에서는 앞에서부터 하나씩 순서대로 접근할 것이고

list만 정렬되어 있다면 별다른 비교없이 i=start와 같이 반복문 범위를 설정해 오름차순을 만족시킬 수 있다.

 

< 초기 코드 2 >

import java.util.*;

public class Main{
    public static List<Character> list=new LinkedList<>();
    public static StringBuilder sb=new StringBuilder();
    public static boolean visited[];
    public static char password[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int l=s.nextInt();
        int c=s.nextInt();
        visited=new boolean[c];
        password=new char[c];
        for(int i=0;i<c;i++){
            list.add(s.next().charAt(0));
        } 
        Collections.sort(list);
        dfs(0,l,0);
        System.out.println(sb);
        
    }
    public static void dfs(int start,int endPoint,int depth){
        if(depth==endPoint){
            for(int i=0;i<password.length;i++){
                sb.append(password[i]);
            }sb.append("\n");
            return;
        }
        
        for(int i=start;i<visited.length;i++){
            if(!visited[i]){
                visited[i]=true;
                password[depth]=list.get(i);
                dfs(i,endPoint,depth+1);
                visited[i]=false;
            }
        }
    }
}

해당 코드는 초기 코드 1에서 불필요한 조건문을 제거해 수정한 코드이다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static List<Character> list=new LinkedList<>();
    public static int cnt=0;
    public static StringBuilder sb=new StringBuilder();
    public static boolean visited[];
    public static char password[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int l=s.nextInt();
        int c=s.nextInt();
        visited=new boolean[c];
        password=new char[l];
        for(int i=0;i<c;i++){
            list.add(s.next().charAt(0));
        } 
        Collections.sort(list);
        dfs(0,l,0);
        System.out.println(sb);
        
    }
    public static void dfs(int start,int endPoint,int depth){
        if(depth==endPoint){
            int cnt=0;
            for(int i=0;i<password.length;i++){
                if(password[i]=='a'||password[i]=='e'||password[i]=='i'||password[i]=='o'||password[i]=='u'){
                    cnt++;
                }
            }
            if(cnt<1||endPoint-cnt<2){
                return;
            }
            for(int i=0;i<password.length;i++){
                sb.append(password[i]);
            }sb.append("\n");
            cnt=0;
            return;
        }
        
        for(int i=start;i<visited.length;i++){
            if(!visited[i]){
                visited[i]=true;
                password[depth]=list.get(i);
                dfs(i,endPoint,depth+1);
                visited[i]=false;
            }
        }
    }
}

최종 코드에서는 초기 코드에서 고려하지 못했던 1번과 2번 조건을 추가해 코드를 완성하였다.

초기 코드의 문제점은 3번 조건에만 매몰되어 1번과 2번을 고려하지 못했다는 것인데

그래서 depth가 endPoint와 같아지면 password에 자음과 모음이 몇개인지 판단해 출력할지 말지를 결정하는 방식으로 

코드르 작성하였다. 

 

  마무리  

해당 문제는 골드 5라는 난이도를 가지고 있어 어렵게 느껴질 수도 있지만  사실 기본적인 dfs에 조건이 조금 추간된 문제이다.

조건을 잘 파악하고 문제를 접근한다면 어렵지 않게 해결할 수 있을 것이라고 생각된다.

 

 

  추가 코드 분석 및 풀이  

여러 풀이들을 찾아보고 확인해보았지만 입출력을 최적화하거나 StringToken를 활용하면 문자를 처리하는 등 

구현의 디테일은 달라도 dfs를 활용하여 문제를 접근하고 자음과 모음을 카운트해 출력할지 말지를 결정하는 부분은 

일맥상통해 추가 코드 분석과 풀이는 넘어가도록 하겠다.