Taxol

I’ve always been.

백준 1759 - 암호 만들기

Updated:

Java

1759 번 - 암호 만들기

문제

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

접근 방법

모음의 개수가 n개 자음의 개수를 m개라고 할때,

  1. 1 ~ n개의 모음을 뽑고 나머지 (L - 모음의 개수)만큼 자음을 뽑는다.
  2. 각각 뽑은 모음 자음을 합쳐서 암호를 만든다.
  3. 만든 암호를 암호 모음에 담는다.
  4. 모두 담겼다면 알파벳 순으로 정렬한다.

따라서, 모음을 뽑는 조합 && 자음을 뽑는 조합으로 총 2개의 조합이 사용되며,
만든 암호 모음을 정렬하는데 Collections.sort()를 사용하였다.

코드

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

public class Main {
	static int L, C;
	static List<Character> vowel, conson;	// 모음 자음
	static char[] pass;
	static List<char[]> result;
	static int Vsize;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	L = stoi(stk.nextToken());
    	C = stoi(stk.nextToken());
    	
    	vowel = new ArrayList<>();			// 모음만 모아 놓아 놓는다.
    	conson = new ArrayList<>();			// 자음만 모아 놓는다.
    	pass = new char[L];					// 완성 된 암호
    	result = new ArrayList<>();			// 모든 암호를 모아 놓는다
    	
    	char tempC;
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < C; i++) {
    		tempC = stk.nextToken().charAt(0);
    		if(tempC == 'a' || tempC == 'e' || tempC == 'o' || tempC == 'u' || tempC == 'i') {
    			vowel.add(tempC);	// 모음
    		}
    		else {
    			conson.add(tempC);	// 자음
    		}
    	}
    	
    	// 만약 모음의 개수가 자음의 개수보다 많은 경우
    	// 모음은 최소 1개부터 뽑아야함, 하지만 자음도 최소한 2개는 뽑아야함
    	Vsize = vowel.size();
    	if(Vsize > L - 2)
    		Vsize = L - 2;
    	
    	
    	for(int i = 1; i <= Vsize; i++) {
    		V_DFS(0, 0, i, new boolean[vowel.size()], new char[i]);
    	}

    	// 모든 암호를 알파벳 순으로 정렬한다.
    	Collections.sort(result, new Comparator<char[]>() {
			@Override
			public int compare(char[] o1, char[] o2) {
				for(int i = 0; i < L; i++) {
					if(Character.compare(o1[i], o2[i]) != 0)
						return Character.compare(o1[i], o2[i]);
				}
				return 0;
			}
		});
    	
    	for(char[] carr : result) {
    		System.out.println(carr);
    	}
    	
    	br.close();
	}
	
	// 모음을 뽑는다.
	static void V_DFS(int lv, int st, int N, boolean[] vis, char[] sel) {
		if(lv == N) {
			C_DFS(0, 0, L - N, new boolean[conson.size()], sel, new char[L-N]);
			return;
		}
		
		for(int i = st; i < vowel.size(); i++) {
			if(!vis[i]) {
				vis[i] = true;
				sel[lv] = vowel.get(i);
				V_DFS(lv + 1, i + 1, N, vis, sel);
				vis[i] = false;
			}
		}
	}
	 
	// 자음을 뽑는다.
	static void C_DFS(int lv, int st, int N, boolean[] vis, char[] Vsel, char[] sel) {
		if(lv == N) {
			int idx = 0;
			for(int i = 0; i < L - N; i++) {
				pass[idx++] =  Vsel[i];
			}
			for(int i = 0; i < N; i++) {
				pass[idx++] = sel[i];
			}
			Arrays.sort(pass);
			result.add(pass.clone());	// 모음과 자음을 합쳐 암호를 만들면, 암호 모음집에 넣는다.
			return;
		}
		for(int i = st; i < conson.size(); i++) {
			if(!vis[i]) {
				vis[i] = true;
				sel[lv] = conson.get(i);
				C_DFS(lv + 1, i + 1, N , vis, Vsel, sel);
				vis[i] = false;
			}
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

잘 알려진 풀이 방법

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

public class Main {
	static int n, result;
	static int L, C;
	static char[] alpha;
	static boolean[] vis;
	static char[] pw;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
    	L = stoi(stk.nextToken());
    	C = stoi(stk.nextToken());
    	
    	stk = new StringTokenizer(br.readLine());
    	alpha = new char[C];
    	pw = new char[L];
    	for(int i = 0; i < C; i++) {
    		alpha[i] = stk.nextToken().charAt(0);
    	}
    	// 미리 알파벳을 정렬한다.
    	// 따라서 뽑히는 암호 순서가 자동적으로 사전 순으로 정렬이 된다.
    	Arrays.sort(alpha);
    	vis = new boolean[C];
    	
    	DFS(0,0);
    	
    	br.close();
	}
	
	static void DFS(int lv, int st) {
		if(lv == L) {		// L개의 알파벳을 뽑는다.
			int vowCnt = 0;
			int conCnt = 0;
			for(int i = 0; i < L; i++) {
				if(isVowel(pw[i])) {	// 모음의 개수 세기
					vowCnt++;
				}
				else {					// 자음의 개수 세기
					conCnt++;
				}
			}
			// 모음이 최소한 1개, 자음이 최소한 2개이면 암호를 출력한다.
			if(vowCnt >= 1 && conCnt >= 2) {
				System.out.println(pw);
			}
			return;
		}
		for(int i = st; i < C; i++) {
			if(!vis[i]) {
				vis[i] = true;
				pw[lv] = alpha[i];
				DFS(lv + 1, i + 1);
				vis[i] = false;
			}
		}
		
	}
	// 모음 자음 판별하는 메서드
	static boolean isVowel(char tempC) {
		if(tempC == 'a' || tempC == 'e' || tempC == 'o' || tempC == 'u' || tempC == 'i') {
			return true;
		}
		return false;
	}
	
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐★★

후기

더 쉬운 방법이 있으니, 그 방법으로 풀어야 한다.

  1. 그 방법은 먼저 모든 알파벳을 정렬한다.
  2. L개의 알파벳을 뽑는다.
  3. 뽑은 알파벳의 각각이 자음이 최소한 2개이상, 모음이 1개 이상이면 바로 암호를 출력한다.

개선할 점

없

You may also enjoy