암호 만들기(BJ_G5_1759)

1. 문제 링크

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

---

 

2. 나의 코드

메모리: 14712kb
시간: 136ms
코드 길이: 1402B
설명: 순열을 사용해서 모든 경우의 수를 구한다. 
시간복잡도 : O(N!)
하지만 만약 그 전의 알파벳과 비교해 정렬이 되지 않은 문자가 있으면 백트래킹을 한다.

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[] alpha;
	static int L, C;
	static char[] input;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		input = new char[L];
		alpha = new char[C];
		isSelected = new boolean[C];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			alpha[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(alpha);
		perm(0);
	}
	
	public static void perm(int cnt) {
		if (cnt == L) {
			if (check()) {
				String str = String.valueOf(input);
				System.out.println(str);
			}
			return;
		}
		
		for (int i = 0; i < C; i++) {
			if (isSelected[i]) {
				continue;
			}
			if (cnt != 0 && alpha[i] - input[cnt - 1] < 0) continue;
			input[cnt] = alpha[i];
			isSelected[i] = true;
			perm(cnt + 1);
			isSelected[i] = false;
		}
	}
	
	public static boolean check() {
		int x = 0, y = 0;
		for (char c : input) {
			if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') x++;
			else y++;
		}
		if (x >= 1 && y >= 2) return true;
		return false;
	}
}

 

---

 

3. 정답 코드

import java.util.Arrays;
import java.util.Scanner;

public class 암호만들기 {
	static int L, C;
	static char[] data;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner("4 6\na t c i s w");
		L = sc.nextInt();
		C = sc.nextInt();
		data = new char[C];
		for (int c = 0; c < C; c++) data[c] = sc.next().charAt(0);
		Arrays.sort(data);
		solve(0, 0, "");
	}
	
	static void solve(int cnt, int start, String ans) {
		if (cnt == L) {
			char[] arr = ans.toCharArray();
			int moCnt = 0, jaCnt = 0;
			for (char c : arr) {
				if (c == 'a' || c == 'i' || c == 'e' || c == 'o' || c == 'u') moCnt++;
				else jaCnt++;
			}
			if (moCnt >= 1 && jaCnt >= 2) System.out.println(ans);				
			return;
		}
		
		for (int i = start; i < C; i++) {
			solve(cnt + 1, i + 1, ans + data[i]);
		}
	}
}

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

public class Main {

    public static int L, C;
    public static char[] list;
    public static char[] code;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        list = new char[C];
        code = new char[L];

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < C; x++) {
            list[x] = st.nextToken().charAt(0);
        }


        // 정렬
        Arrays.sort(list);

        makeCode(0,0);

    }

    public static void makeCode(int x,int idx) {


        if (idx == L) {
            // 최소 한개의 모음, 최소 2개의 자음인지 확인
            if (isValid()) {
                System.out.println(code);
            }
            return;
        }

        // 아직 길이 L의 코드를 만들지 않았고 글자도 아직 남았다.

        for (int i = x; i < C; i++) {
            code[idx] = list[i];
            makeCode(i+1, idx + 1);
        }
    }

    // 최소 모음 1개, 최소 자음 2개인지 확인
    public static boolean isValid() {
        int mo = 0;
        int ja = 0;

        for (char x : code) {
            if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
                mo++;
            } else {
                ja++;
            }
        }

        if (mo >= 1 && ja >= 2) {
            return true;
        }
        return false;
    }

}

 

---

 

4. 배운 점

- 정렬을 한 후 순열을 사용하지 않고 조합을 사용하면 어짜피 뒤에 있는 알파벳이 사전순이라는 것을 알았다. 무의미한 순열을 한 것이다.