[BOJ] 1759 암호 만들기 [Java]

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

1759번: 암호 만들기

---

1. 문제 요약

서로 다른 C개의 알파벳 소문자 중 L개를 선택하여 암호를 생성한다.

* 암호는 최소 1개의 모음(a,e,i,o,u), 최소 2개의 자음을 포함한다.

* 암호는 증가하는 순서이다.

가능성 있는 암호를 모두 구하라.

 

2. 풀이

처음에는 순열로 접근하였다. C개 중 L개를 뽑는데, 순서를 고려해야 한다고 생각했다.

하지만 그럴 필요가 없었다. C개의 알파벳을 먼저 배열해놓고, 거기서 L개만 뽑으면 된다.

조합을 사용하여 푸는 문제이다.

그렇다면, 모든 순열 문제를 처음에 정렬해놓고 거기서 개수대로 뽑는 조합을 사용해도 되는건가? 

=> 순열은 줄세우는 경우의 수이다. 5명의 가수의 무대 순서를 정한다고 생각해보자.

5명의 가수를 정렬해놓고 뽑는다는건 말도 안될 뿐더러 모든 경우의 수를 생각해야 하므로 의미가 없다.

=> 이 문제가 특이한 케이스다. 알파벳의 특성상 정렬이 가능하다. 따라서 알파벳을 정렬된 순서로 뽑아야 한다면, 
알파벳을 정렬해놓고 개수대로 뽑으면 된다. 순서를 우리가 고려하지 않아도 되는 것이었다.

 

1. 알파벳이 담긴 src 배열을 먼저 오름차순 정렬한다.

2. 정렬된 알파벳 중 L개를 뽑는 조합을 수행한다.

• 여기서 주의할 점은, 모음과 자음을 신경써줘야 하는 것이다.
• 전형적인 조합 틀은 두가지 경우로 나누어 재귀를 수행한다.
  • 인덱스를 선택하고 끝까지 조합을 만드는 경우 => 조합인덱스 + 1
  • 인덱스를 선택하지 않고 끝까지 조합을 만드는 경우 => 조합인덱스 (선택안해서 덮어씀)
• 여기서는 지금 인덱스가 모음인지, 자음인지를 먼저 보고,
  • 모음일 때 선택하고  조합을 끝까지 만든다   => 조합인덱스 + 1, 모음 개수 + 1 
  • 모음일 때 선택하지 않고 조합을 끝까지 만든다   => 조합인덱스 , 모음 개수
  • 자음일 때 선택하고 조합을 끝까지 만든다   => 조합인덱스 + 1, 자음 개수 + 1 
  • 자음일 때 선택하지 않고 조합을 만든다  => 조합인덱스, 자음 개수
• 경우의 수가 늘어났기 때문에, 기존의 2번의 재귀가 4번의 재귀로 늘어나는 것이다. 
• 모음개수, 자음개수가 왔던 길을 다시 가는 백트래킹에 의해 계속해서 갱신되어야 하므로
  파라미터로 전달하여 개수를 갱신해준다.
• 기저조건으로, L개의 알파벳을 다 뽑았을 경우 재귀함수는 return 된다.
  여기서 complete code로, 모음개수가 1개 이상, 자음개수가 2개 이상인 조합은 조건을 만족하므로 출력해준다.
• 시간복잡도는 2초 제한이며 (3 ≤ L ≤ C ≤ 15) 범위를 만족한다.
  최악의 경우를 생각해봤을 때 15C7 = 15! / 7!*8! = 6435이다.
  순열로 순서까지 고려해서 풀었을 경우, 15P7 = 15! / 8! = 259459200이다.
  => 차이가 많이 난다. 순서를 고려할 필요가 없으면 고려하지 않고 조합을 사용하는 방향으로 풀자.

 

 

3. 문제점

 

 

4. 코드

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

public class BOJ_1759_암호만들기 {

	static char[] src, tgt;
	static int N, M;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		tgt = new char[M]; //조합 배열
		src = new char[N]; //알파벳 후보 배열
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			src[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(src); //정렬을 해주고 조합 수행
		
		comb(0, 0, 0, 0);
	}
	
	static void comb(int tgtIdx, int srcIdx, int moCnt, int jaCnt) {
		if (tgtIdx == M) { //기저조건1. 조합 M개를 완성했을 때
			//complete code
			if (moCnt >= 1 && jaCnt >= 2) { //모음 1개 이상, 자음 2개 이상 -> 만족
				for (int i = 0; i < M; i++)
					System.out.print(tgt[i]);
				System.out.println();
			}
			
			return;
		}
		
		if (srcIdx == N) return; //기저조건2. N개의 알파벳을 모두 봤을 때
		
		tgt[tgtIdx] = src[srcIdx]; //조합에 넣어줌
		
		//4번의 재귀
		if (tgt[tgtIdx] == 'a' ||tgt[tgtIdx] == 'e' ||tgt[tgtIdx] == 'i' ||tgt[tgtIdx] == 'o' ||tgt[tgtIdx] == 'u') {
			comb(tgtIdx + 1, srcIdx + 1, moCnt+1, jaCnt); //모음 선택하고 쭉 간 경우
			comb(tgtIdx, srcIdx + 1, moCnt, jaCnt); //모음이지만 선택 안하고 쭉 같 경우
		}
			
		else {
			comb(tgtIdx + 1, srcIdx + 1, moCnt, jaCnt+1); //자음선택하고 쭉 간 경우
			comb(tgtIdx, srcIdx + 1, moCnt, jaCnt); //자음이지만 선택 안하고 쭉 간 경우
		}
		
	}
}