[백준] BOJ 1759 암호 만들기(자바/메모리 초과 해결)

 

엄청 어려운 문제는 아니었으나, 메모리 초과 났던 문제이다.

 

 

문제 풀이

 

 

가능성 있는 암호들을 모두 구해야 하므로 조합을 통해 모든 경우의 수를 확인해야겠다고 생각했다. 

 

 

따라서, 조합을 통해 나올 수 있는 문자열 조합을 구한 다음 해당 문자열이 최소 모음 1개, 자음 2개를 포함하는지를 확인했다.

 

 

 

 

하지만, 다음과 같이 메모리 초과가 발생했다.. 

 

 

 

 

이유를 모르겠어서 다른 블로그에서 아이디어를 참고했고,  이번에는 통과할 수 있었다.

 

 

 

 

 

 

내가 메모리 초과를 해결할 수 있었던 방법은 다음과 같다.

 

 

 

 

우선 나는 조합을 만들때, for문에서 0번 인덱스부터 시작해서 방문체크를 확인하면서 문제를 풀었다.

다음과 같이 말이다.

for (int i = 0; i < C; i++) {
	if(!visited[i]){
		visited[i] = true;
		output[totalCnt] = i;
		solve(totalCnt+1, visited, output, i);
		visited[i] = false;
	}
}

 

 

이 부분에 대해서 먼저 입력받은 배열을 정렬시켜 주었다. 

 

Arrays.sort(input);

 

 

 

정렬을 시켜주면 0번부터 시작안하고, 현재 인덱스부터 시작하면 알아서 정렬된 문자열을 만들어준다.

기존에는 0번부터 시작하고, 문자열이 만들어지면 그 문자열이 정렬되었는지도 확인했었는데 그럴 필요가 없어졌다.

 

for (int i = now; i < C; i++) {
	if(!visited[i]){
		visited[i] = true;
		output[totalCnt] = i;
		solve(totalCnt+1, visited, output, i);
		visited[i] = false;
	}
}

 

 

 

 

 

 

---

문제 구현

public class Main_1759 {
	static int L, C;
	static LinkedList<Character> alphabet = new LinkedList<Character>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
	static char[] input;
	static StringBuilder sb;
	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());

		st = new StringTokenizer(br.readLine());

		input = new char[C];

		for (int i = 0; i < C; i++) {
			input[i] = st.nextToken().charAt(0);
		}

		Arrays.sort(input);

		sb = new StringBuilder();
		solve(0, new boolean[C], new int[L], 0);

		String[] results = sb.toString().split("\n");


		Arrays.stream(results).forEach(s -> System.out.println(s));
	}

	static void solve(int totalCnt, boolean[] visited, int[] output, int now){
		if(totalCnt == L){
			//조합된 문자열이 모음 1개, 자음 2개를 포함하는지 확인
			String concatTxt = concat(output);
			if(check(concatTxt)){
				sb.append(concatTxt);
				sb.append("\n");
			}
			return;
		}

		for (int i = now; i < C; i++) {
			if(!visited[i]){
				visited[i] = true;
				output[totalCnt] = i;
				solve(totalCnt+1, visited, output, i);
				visited[i] = false;
			}
		}

	}

	static String concat(int[] output){
		StringBuilder builder = new StringBuilder();

		for (int i = 0; i < output.length; i++) {
			builder.append(input[output[i]]);
		}

		return builder.toString();
	}

	static boolean check(String txt){
		int cnt1 = 0, cnt2 = 0;
		for (int i = 0; i < txt.length(); i++) {
			if(alphabet.contains(txt.charAt(i))){
				cnt1++;
			}else{
				cnt2++;
			}
		}
		if(cnt1 >= 1 && cnt2 >= 2) return true;

		return false;
	}
}