[문제풀이] B1759 암호만들기

암호만들기

---

  🪅 오름차순을 보고, 배열을 정렬한 다음, 조합을 이용할 생각을 할 줄 아느냐 => 이전 고른 인덱스보다 큰 인덱스를 고르는 '조합'  
  🪅 조합을 구현할 줄 아는가 => '백트래킹'을 할 줄 아는가

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static char[] arr;
    static int L;
    static int C;
    static int[] selection;
    static boolean[] isSelected;
    public static boolean checkValid() {
        int vowelCnt = 0;
        int consoCnt = 0;
        for(int i = 0; i < L; i++) {
            char c = arr[selection[i]];
            switch(c) {
                case 'a':
                case 'e':
                case 'i':
                case 'o':
                case 'u':
                    vowelCnt++;
                    break;
                default:
                    consoCnt++;
            }
            if(vowelCnt >= 1 && consoCnt >= 2) {
                return true;
            }
        }
        return false;
    }
    public static void combination(int r, int start) {
        if(r == L) {
            if(checkValid()) {
                for(int i = 0; i < L; i++) {
                    System.out.print(arr[selection[i]]);
                }
                System.out.println();
            }
            return;
        }
        for(int i = start; i < C; i++) {
            if(isSelected[i]) continue;
            isSelected[i] = true;
            selection[r] = i;
            combination(r+1, i);
            isSelected[i] = false;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        L = Integer.parseInt(token.nextToken());
        C = Integer.parseInt(token.nextToken());

        arr = new char[C];
        selection = new int[L];
        isSelected = new boolean[C];

        token = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < C; i++) {
            arr[i] = token.nextToken().charAt(0);
        }
        Arrays.sort(arr);
//        System.out.println(Arrays.toString(arr));
        combination(0,0);
    }
}

💡 문제 접근 과정
알파벳이 증가하는 순서로 배열될 것이라는 조건에서 완전탐색 중 조합을 쓸 생각을 했다
(이전 고른 인덱스보다 큰 인덱스를 고르는)
하지만, 그전에 오름차순으로 정렬해놓는 것이 중요하다.
그런 다음, 문제의 나머지 조건을 만족하는 조합만을 따로 출력한다.