[BOJ] 1062. 가르침

재귀를 이용한 기본 구현

• 메모리 : 14,996 KB
• 시간 : 256 ms
• 코드길이 : 1,616 B
• 소요시간 : 2H 15M
• 더 배워야할 문자만 추려서 재귀를 돌리려고 하였는데 오히려 시간초과가 떳다. 이미 배웠는지 확인하고 ArrayList에 없을 경우에만 추가해주는 부분이 시간 소요가 오히려 많은 것 같다.

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

public class Main_B_1062_가르침 {

	static int N, K;
	static int answer, alphSize = 26;
	static String[] words;
	static boolean[] alpha;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		answer = Integer.MIN_VALUE;
		words = new String[N];
		alpha = new boolean[alphSize];
		alpha['a' - 'a'] = alpha['c' - 'a'] = alpha['i' - 'a'] = alpha['n' - 'a'] = alpha['t' - 'a'] = true; // acint 미리 카운트

		for (int n = 0; n < N; n++) {
			String tmp = in.readLine();
			words[n] = tmp.substring(4, tmp.length() - 4);
		}

		if (K < 5) {
			System.out.println(0);
		} else if (K >= alphSize) {
			System.out.println(N);
		} else {
			K -= 5;
			recursive(0, 0);
			System.out.println(answer);
		}
	}

	private static void recursive(int index, int count) {
		if (answer == words.length)
			return;

		if (count == K) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				boolean check = true;
				for (int j = 0; j < words[i].length(); j++) {
					if (!alpha[words[i].charAt(j) - 'a']) {
						check = false;
						break;
					}
				}
				if (check)
					cnt++;
			}
			answer = Integer.max(answer, cnt);
			return;
		}

		for (int i = index; i < alphSize; i++) {
			if (!alpha[i]) {
				alpha[i] = true;
				recursive(i, count + 1);
				alpha[i] = false;
			}
		}

	}
}

비트 마스크(BitMask)

• 메모리 : 13,552 KB
• 시간 : 120 ms
• 코드길이 : 1,513 B
• 소요시간 : 30M
• 메모리 차이가 큰건 아니지만 시간은 거의 절반으로 줄었다. 메모리와 시간면에서 비트마스크가 훨씬 효율적이다.

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

public class Main_B_1062_가르침_2차 {

	static int N, K, alpha;
	static int answer, alphSize = 26;
	static int[] words;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		answer = Integer.MIN_VALUE;
		words = new int[N];

		for (int n = 0; n < N; n++) {
			String tmp = in.readLine();
			for (int i = 4; i < tmp.length() - 4; i++) {
				words[n] |= (1 << (tmp.charAt(i) - 'a'));
			}
		}

		if (K < 5) {
			System.out.println(0);
		} else if (K >= alphSize) {
			System.out.println(N);
		} else {
			alpha = 0;
			alpha |= (1 << ('a' - 'a'));
			alpha |= (1 << ('c' - 'a'));
			alpha |= (1 << ('i' - 'a'));
			alpha |= (1 << ('n' - 'a'));
			alpha |= (1 << ('t' - 'a'));
			K -= 5;
			recursive(0, 0);
			System.out.println(answer);
		}
	}

	private static void recursive(int index, int count) {
		if (answer == N)
			return;

		if (count == K) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				if ((alpha | words[i]) == alpha)
					cnt++;
			}
			answer = Integer.max(answer, cnt);
			return;
		}

		for (int i = index; i < alphSize; i++) {
			if ((alpha & (1 << i)) == 0) {
				alpha |= (1 << i);
				recursive(i, count + 1);
				alpha ^= (1 << i);
			}
		}

	}
}