문제

BOJ 1759: 암호 만들기 https://www.acmicpc.net/problem/1759

풀이

조건

• 조합한 암호는 최소 1개의 모음과 최소 2개의 자음이 포함되어야 한다.
• 암호의 길이는 L개 이다.
• 암호는 알파벳 순서로 오름차순이어야 한다.

풀이 순서

• 문자를 입력받고 오름차순으로 정렬한다.
• 정렬한 문자 중 모음이 어디에 있는지 구분 해 준다.
• 백트래킹으로 해결한다.
  • 암호의 길이(depth), 모음의 갯수(momCnt), 자음의 갯수(sonCnt)로 종료 조건을 만든다.
  • 방문처리를 하여 문자가 중복으로 조합되지 않도록 한다.
  • 현재 문자가 모음인지 자음인지 구분하여 재귀호출 시 전달인자로 넘겨준다

코드

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

public class Main {
	
	static int L, C;
	static char[] password, input; // 출력할 배열과 입력 받은 문자 넣을 배열
	static boolean[] isMom; // 모음 인지 체크할 배열
	static boolean[] isChecked; // 방문 처리 할 배열
	static StringBuilder sb = new StringBuilder();
	
	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[C]; // 입력받은 암호가 될 수 있는 문자 배열
		isChecked = new boolean[C]; // 방문 처리 할 배열
		isMom = new boolean[C]; // 모음 체크 할 배열
		password = new char[C]; // 출력할 암호 배열
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<input.length; i++) {
			input[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(input); // 알파벳이 증가하는 순서로 배열됨
		
		// 모음은 true 처리
		for(int i=0; i<input.length; i++) {
			if(input[i] == 'a' || input[i] == 'e' || input[i] == 'i' || input[i] == 'o' || input[i] == 'u') {
				isMom[i] = true;
			}
		}
		
		bt(0, 0, 0, 0);
		System.out.println(sb);
	}
	
	static void bt(int depth, int start, int momCnt, int sonCnt) {
		/*
		 * depth: 조합된 암호의 길이
		 * start: 조합할 암호가 알파벳 순으로 오름차순으로 나올 수 있도록 함
		 * momCnt: 모음의 갯수
		 * sonCnt: 자음의 갯수
		 */
		
		// 조합된 암호의 길이가 L && 모음의 수가 1개 이상 && 자음의 수가 2개 이상
		if(depth == L && momCnt >= 1 && sonCnt >= 2) {
			for(int i=0; i<L; i++) {
				sb.append(password[i]);
			}
			sb.append("\n");
			
			return;
		}
		
		for(int i=start; i<input.length; i++) {
			int mom = momCnt;
			int son = sonCnt;
			// 아직 방문하지 않은 문자라면?
			if(!isChecked[i]) {
				if(isMom[i]) { // 현재 문자가 모음이면 모음 갯수 +1
					mom++;
				} else { // 현재 문자가 자음이면 자음 갯수 +1
					son++;
				}
				// 현재 문자를 방문처리 해주고 재귀호출 할 수 있도록 함
				isChecked[i] = true;
				// 암호 조합 배열에 현재 문자 넣음
				password[depth] = input[i];
				// 재귀 호출
				bt(depth + 1, i, mom, son);
				// for문의 다음 i를 위해 방문처리 해제
				isChecked[i] = false;
			}
		}
	}
}

정리

• 조건을 잘 따져서 해결하자
  • 모음과 자음의 갯수가 조건에 있었는데 빼먹고 풀었다가 틀렸다
• 조합한 암호 배열의 길이를 잘 못 잡아서 런타임 에러 (ArrayIndexOutOfBounds)가 발생했다.
  • 출력할 배열의 길이가 L 이라고 L로 잡으면 안된다.