/ BOJ

BOJ_1759_암호만들기_JAVA

문제 : 암호만들기

링크 : BOJ_1759_암호만들기

접근 방식

백트래킹 문제인데, 조합을 이용해서 푸는 문제라고 한다. 나는 이런 내용을 순열로 풀고 나서 알게 되었다. 나는 순열을 구하면서 가지치기를 통해 원하는 값을 리스트에 넣고, 그 리스트를 정렬하여 사전순으로 만들었다.

C 개의 알파벳으로부터 L개의 길이의 암호문을 구하는 문제이다. 암호의 조건으로는 2가지가 있는데, 1가지는 왼쪽의 알파벳부터 오른쪽으로 갈 수록 값이 증가한다는 것, abc는 가능하지만 bac는 불가능하다.

2번째 조건은 알파벳의 모음(a,e,i,o,u)은 최소 1개 이상 암호문에 포함되어야하며, 자음은 최소 2개 이상 암호문에 포함되어야 한다는 조건이다.

나는 암호에 순서가 있다고 생각하여 순열을 이용하여 풀이해주었다.

풀이 방법

  1. 먼저 값을 저장할 변수들을 전역으로 선언해주었다.

  2. 알파벳의 개수와 암호문의 길이를 읽어와 변수에 저장한다.

  3. 주어진 문자열을 읽어들일 배열을 생성해 값을 할당하고, 암호문 경우의 수를 저장할 배열을 암호문의 길이 L의 크기로 생성했다.

  4. 순열을 통해 경우의 수를 구하는데, 가지치기의 조건을 둔다.

  5. 가지치기의 조건은, 현재 알파벳이 다음 알파벳보다 작을 경우에만 재귀호출을 하도록 하는 것이다.

  6. 순열이 완성되면, 각 순열별로 자음 카운트와 모음 카운트를 저장할 변수를 생성한다.

  7. 만들어진 순열을 탐색하는데, 알파벳이 모음이면 모음 카운트를 증가시키고, 자음이라면 자음 카운트를 증가시킨다.

  8. 순열의 순회가 끝나고, 모음카운트가 1 이상, 자음카운트가 2 이상이라면 해당하는 수열을 문자열로 만들어 String 타입 리스트에 저장한다.

  9. 순열이 모두 구해진 후, String 리스트를 Collections.sort 메서드를 이용하여 정렬한 후 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_1759_암호만들기 {
	static int C;
	static int L;
	static char[] chars;
	static char[] answer;
	static StringBuilder sb = new StringBuilder();
	static List<String> strs = new ArrayList<>();
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

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

		chars = new char[C];
		answer = new char[L];
		st = new StringTokenizer(in.readLine()," ");
		for(int i=0;i<C;i++) {
			chars[i] = st.nextToken().charAt(0);
		}

		perm(0,0,' ');
		Collections.sort(strs);

		for(int i=0;i<strs.size();i++) {
			sb.append(strs.get(i)).append('\n');
		}
		System.out.print(sb);
	}

	public static void perm(int cnt, int flag, char n) {

		if(cnt == L) {
			int mCnt = 0;
			int jCnt = 0;
			for(int i=0;i<L;i++) {
				switch(answer[i]) {
				case 'a':
				case 'e':
				case 'i':
				case 'o':
				case 'u':
					mCnt++;
					break;
				default:
					jCnt++;
				}
			}
			if(mCnt >= 1 && jCnt >= 2) {
				String str = "";
				for(int i=0;i<L;i++) {
					str = str + answer[i];
				}
				strs.add(str);
			}
			return;
		}


		for(int i=0;i<C;i++) {
			if((flag & 1<<i) != 0) {
				continue;
			}
			answer[cnt] = chars[i];
			// 가지치기 1 현재 알파벳이 다음 알파벳보다 작을 경우에만 재귀,
			if(n < answer[cnt]) {
				perm(cnt+1,flag | 1<<i, answer[cnt]);
			}
		}

	}

}