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

[백준]1759: 암호 만들기

www.acmicpc.net/problem/1759

1759번: 암호 만들기

풀이

순열을 사용한 백트랙킹문제!

 

결과가 사전 순서대로 저장되어야 하므로 sort를 해주었다. 그리고 값을 뽑을때 알파벳이 증가하는 순서대로만 뽑아야 하므로 compareTo 메소드를 사용하여 이전의 뽑은 값과 비교해 주었다. 또한 모음인지 체크하는 함수를 만들어 주었고 조건에 모든 문자를 다 뽑은 후에는 모음의 수, 자음의 수가 조건에 맞는지 확인한 후 맞다면 출력하도록 해주었다. 

 

별로 어렵지 않은 전형적인 순열 문제였다-!

 

코드

import java.util.*;
 
public class Main {    
    
    static String[] text;
    static int l, c;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        l = scan.nextInt();
        c = scan.nextInt();
        scan.nextLine();
        
        String str = scan.nextLine();
        text = str.split(" ");
        Arrays.sort(text);
        
        String[] result = new String[l];
        visited = new boolean[c];
        permutation(result, 0, 0, 0);
    }    
    
    public static void permutation(String[] result, int idx, int vowel, int consonant) {
        if(idx == l) {
            if(vowel >= 1 && consonant >= 2) {
                for(int i = 0; i < l; i++) {
                    System.out.print(result[i]);
                }
                System.out.println();
            }
            return;
        }
        
        for(int i = 0; i < c; i++) {
            if(visited[i] == false) {
                //이전에 뽑았던 값보다 사전순으로 더 큰값을 뽑아야 하며 처음 뽑는 경우에는 상관없다.
                if(idx == 0 || result[idx - 1].compareTo(text[i]) < 0) { 
                    visited[i] = true;
                    result[idx] = text[i];
                    if(isVowel(text[i])) permutation(result, idx + 1, vowel + 1, consonant);
                    else permutation(result, idx + 1, vowel, consonant + 1);
                    visited[i] = false;
                }
            }
        }
    }
    
    //모음체크
    public static boolean isVowel(String s) {
        if(s.equals("a") || s.equals("e") || s.equals("i") || s.equals("o") || s.equals("u")) {
            return true;
        }
        return false;
    }
}