백준 1759번 - 암호 만들기

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

굉장히 오랜만에 포스팅하네요.

 

그동안 문제를 안 푼건 아니지만 이것저것 할일이 있다보니 포스팅이 뜸해졌습니다.

 

물론 다 변명입니다만 :)

 

 

이번 문제는 언뜻 보면 문자열 문제같아 보이지만...

그냥 조합 문제입니다.

 

다만 그냥 조합은 아니고 조건이 붙은 조합입니다.

 

문제를 읽어보자면 주어진 문자들을 사용해 정해진 길이로 만들 수 있는 가능한 모든 암호의 경우의 수를 구하는데,

여기서 오름차순으로 이미 순서가 정해져 있는 점에서 순열이 아닌 조합임을 알 수 있습니다.

 

또한, 자음은 최소 2개, 모음은 최소 1개가 포함되어야 한다는 조건이 붙습니다.

재귀 형태로 makeCombination을 만들어 마지막에 return할 때 조건을 확인하는 식으로 풀어도 무방합니다만,

저는 0과 1로 이루어진 배열과 nextPermutation을 이용해 한번 nextPermutation이 실행될 때마다

한가지의 경우가 등장하도록 만들어, do while 문에서 String의 contains method를 사용하여 해당 조건을

만족하는지 체크하였습니다.

 

그런데 다시 문제가 생깁니다. makeCombination으로 풀었을 때는 알아서 오름차순일 것을

nextPermutation으로 풀어버리니 내림차순으로 바뀌어버린 것이지요.

 

그래서 Stack을 사용해 나온 값들을 차례차례 쌓은 후 다시 뽑은 순으로 출력함으로써 내림차순을 오름차순으로 다시 변경해주었습니다.

 

아래는 제가 제출한 코드입니다.

 

 

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

public class Main_BJ_1759_암호만들기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		StringBuffer sb = new StringBuffer();
		
		int L = Integer.parseInt(tk.nextToken());
		int C = Integer.parseInt(tk.nextToken());
		
		// 모음
		char[] A = new char[5];
		int indexA = 0;
		
		// 자음
		char[] B = new char[C];
		int indexB = 0;
		
		char[] inputChar = new char[C];
		tk = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < C; i++) {
			char temp = tk.nextToken().charAt(0);
			inputChar[i] = temp;
			if(temp == 'a' || temp == 'e' || temp == 'i' || temp == 'o' || temp == 'u') {
				A[indexA++] = temp;
			}else {
				B[indexB++] = temp;
			}
		}
		
		Arrays.sort(inputChar);
		
		int[] input = new int[C];
		
		for(int i = 0; i < L; i++) {
			input[C-1 - i] = 1;
		}

		Stack<String> strStack = new Stack<>();
		
		do {
			char[] list = new char[L];
			int index = 0;
			for(int i = 0; i < C; i++) {
				if(input[i] == 1) list[index++] = inputChar[i];
			}
			
			String str = String.valueOf(list);

			boolean jud = false;
			int jud2 = 0;
			for(int j = 0; j < indexA; j++) {
				if(str.contains(String.valueOf(A[j]))) {
					jud = true;
				}
			}
			if(jud2 <2) {
				for(int j = 0; j < indexB; j++) {
					if(str.contains(String.valueOf(B[j]))){
						jud2++;
					}
				}
			}
			
			if(jud && jud2 >= 2) strStack.push(str);
			
		}while(nextPermutation(input, C));
		
		
		while(!strStack.empty()) {
			sb.append(strStack.pop()).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	private static boolean nextPermutation(int[] arr, int N) {
		int i = N - 1;
		while(i > 0 && arr[i-1] >= arr[i]) i--;
		if(i == 0) return false;
		
		int j = N - 1;
		while(arr[i-1] >= arr[j]) j--;
		swap(arr, i-1, j);
		
		int k = N - 1;
		while(i < k) {
			swap(arr, i++, k--);
		}
		return true;
	}
	
	private static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

}