[백준 1759번 / java] 암호 만들기

문제

1759번: 암호 만들기 (acmicpc.net)

 

조건 :
1. 암호: 서로 다른 L개의 알파벳 소문자
2. 최소 1개의 모음(a e i o u), 최소 2개의 자음
3. 알파벳이 증가하는 순서로 배열되어있음 **놓칠뻔한 조건**암호가 acb가 되면 안 된다.
4. 암호로 사용하는 문자의 종류는 C가지
5. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하라
6. 사전 순으로 출력하라

 

입력 :
4개의 알파벳 소문자, 6개의 문자 종류
a t c i s w (6개의 문자 종류)

풀이1

접근 알고리즘 :

입력값의 범위가 3에서 15로 작으므로 브루트포스를 사용한다.

브루트포스로 모든 조합을 검사하는 과정에서 백트래킹으로 시간복잡도를 줄여준다.

 

처음에는 모음 1개, 자음 2개를 미리 정해놓고 남는 자리에 놓일 알파벳을 찾으려고 했다.

그러나 로직을 짜지 못했을 뿐더러 브루트포스도 아니다.

 

그래서 C개의 알파벳 중 L개의 알파벳을 고른 후, 모음 1개, 자음 2개가 있는지 검사하는 방법으로 변경하였다.

(풀이2 참고)

 

코드1

import java.io.*;
import java.util.*;

public class boj_1759 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        String[] vowels = new String[15];
        String[] consonants = new String[15];

        int count1 = 0, count2 = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<C; i++){
            String s = st.nextToken();
            if(s.equals("a")||s.equals("e")||s.equals("i")||s.equals("o")||s.equals("u")){
                vowels[count1++] = s;
            }else consonants[count2++] = s;
        }
        Arrays.sort(vowels);
    }
    static void choose(String[] vowels, String[] consonants){
        //모음 1개, 자음 2개를 미리 선택
        for(int i=0; i<vowels.length; i++){
            for(int j=0; j<consonants.length; j++){
                for(int j2=j; j2< consonants.length; j2++){
                    String v = vowels[i];
                    String c1 = consonants[j];
                    String c2 = consonants[j2];
                    
                }
            }
        }
    }
}

풀이2

• 입력받은 알파벳을 배열에 넣고 오름차순으로 정렬한다.
  • 오름차순으로 정렬하는 이유는 암호는 무조건 알파벳이 증가하는 순서로 배열되어있기 때문이다.
  • 정렬된 배열의 앞에서부터 차례로 L개씩 알파벳을 선택하면 된다.
• choose() : 앞에서부터 하나씩 알파벳을 선택한다.
  • 알파벳을 하나 선택했으면 임시로 만든 배열에 선택한 알파벳을 넣고, 다음 알파벳을 선택하기 위해 재귀호출한다.
  • 재귀호출 시 현재 선택한 알파벳의 위치+1 (i+1), 현재까지 몇 개의 알파벳을 선택했는지(count+1), 알파벳이 담긴 임시 배열(tmp)을 넘겨준다.
  • 임시 배열을 사용한 이유는 가지치기하며 백트래킹할 때, 가지마다 다른 경우의 배열을 만들어주기 위함이다. 
  • count가 L과 같아지면 isValid()로 모음1, 자음2개 이상인지 확인한 후 만족하면 StringBuilder에 append한 후 재귀를 종료한다.
• save() : L개의 알파벳이 모두 선택되었으면 Stringbuilder에 append한다.
  • choose()에서 처음에 받은 배열은 표준입력으로 들어온 알파벳들이 모두 담긴 arr배열이다. 
  • arr배열은 길이가 C이다. 암호가 될 수 있는 모든 알파벳이 다 들어있다.
  • 다음 알파벳을 선택할 때 참조하는 배열은? 인자로 받은 arr배열
  • 선택된 알파벳을 저장하는 배열은? 인자로 받은 arr배열을 복사한 임시배열
  • 이므로, 계속해서 길이가 C인, 처음 표준입력으로 받은 값이 다 적혀있는 arr배열에다가 선택된 알파벳을 덮어씌우면서 저장하고 있으므로
  • save()함수는 count==L이 된 후 완성된 배열의 모든 값을 StringBuilder에 저장하는 게 아니라, 0부터 L까지의 값만 저장해야 한다.
  • 물론 save()함수가 완성된 배열의 모든 값을 StringBuilder에 저장하게 하는 방법도 있다.
  • 다음 알파벳을 선택할 때 참조하는 배열을 static으로 선언된 arr로 하고, 재귀 인자로 넘기는 임시 배열을 길이가 L인 새로운 배열로 만들어도 된다.

코드2

import java.io.*;
import java.util.*;

public class boj_1759 {
    static String[] arr;
    static int C, L;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

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

        }
        Arrays.sort(arr);
        choose(0,0,arr);
        bw.write(sb+" ");
        bw.close();
    }
    static void choose(int start, int count, String[] arr){
        if(count == L){
            if(isValied(arr))
                save(arr);
            return;
        }
        for(int i=start; i<C; i++){
            String[] tmp = copy(arr);
            tmp[count] = arr[i];
            choose(i+1, count+1, tmp);
        }
    }
    static void save(String[] arr){
        for(int i=0; i<L; i++){
            sb.append(arr[i]);
        }
        sb.append("\n");
    }
    static boolean isValied(String[] arr){
        int countVowels = 0;
        int countConsonants = 0;
        for(int i=0; i<L; i++){ //모음 확인
            if(arr[i].equals("a")|| arr[i].equals("e")||
                    arr[i].equals("i")|| arr[i].equals("o")|| arr[i].equals("u")){
                countVowels++;
            }else countConsonants++;
        }
        if(countVowels >=1 && countConsonants >=2) return true;
        return false;
    }
    static String[] copy(String[] arr){
        String[] ret = new String[arr.length];
        for (int i=0; i<arr.length; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

}