[백준 1759] 암호만들기 -Java

 

 

문제링크 : https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

내 마음대로 풀이

먼저 알파벳을 오름차순으로 sorting 하고

거기서 DFS를 통해 가능한 조합을 찾아냈다.

그런데 자꾸 문제가 틀렸다고 나와서 봤더니,

모음이 1개 이상있어야 하고, 자음이 2개이상 있어야 하는 요구사항을 지키지 않았다.

그 부분을 체크하는 함수를 구현하여 알고리즘을 완성했다.

 

import java.util.Scanner;
import java.util.Arrays;
public class Main
{
    static int key_len = 0;
	static int tot_len = 0 ;
	static char [] cypher;
	public static void main(String[] args) {
	    String line = new String();
	    Scanner sc = new Scanner(System.in);
	    
	    line = sc.nextLine();
	    key_len = Integer.parseInt(line.split(" ")[0]);
	    tot_len = Integer.parseInt(line.split(" ")[1]);
	    
	    cypher = new char[tot_len];
	    
	    line = sc.nextLine();
	    
	    for (int i = 0 ; i < tot_len ; i++)
	    {
	        cypher[i] = line.split(" ")[i].charAt(0);
	    }
	    Arrays.sort(cypher);
	    
	    dfs(-1,0, "");
	}
	
	public static void dfs(int index, int length, String now)
	{
	   if (length == key_len)
	   {
	       if (moem_cnt(now) >= 1 && (key_len - moem_cnt(now)>=2))
	            System.out.println(now);
	        return;
	   }

	   String before = now ;
	   
	   for (int i = 1 ; index + i < tot_len ; i++ )
	   {
	            now += cypher[index+i]; 
	            dfs(index+i,length+1,now);
	            now = before;
	   }
	}
	
	public static int moem_cnt(String now)
	{
	    char [] chs = now.toCharArray();
	    int cnt = 0;
	    
	    for (int i = 0 ; i < chs.length ; i++)
	    {
	        if (chs[i] == 'a' || chs[i] == 'e' || chs[i] == 'i'|| chs[i] == 'o'||
	        chs[i] == 'u')
	        cnt++;
	    }
	    
	    return cnt;
	}
}