[JAVA] 백준 1062번 : 가르침

 

---

 

• 생각

1. 문자 앞 4, 뒤 4를 제외한 문자열만 문자열 배열에 가져와서, a~z개 모든 조합의 6개를 dfs를 통해 돌리면서 확인한다. ==>> 해봤는데 시간초과 뜸.

===>>> 시간초과 뜬 이유는 기존 알파벳 5개를 제외한 나머지 알파벳으로 dfs를 돌려야 했다. (문제 잘못 이해...)

 

 

• 코드

정답 코드 : dfs를 통해 K - 5 개의 모든 알파벳 조합을 돌렸다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int maxValue, N, K;
	static String[] s;
	static boolean[] check;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		maxValue = 0;
		s = new String[N];
		check = new boolean[26];

		// 무조건 배워야하는 단어 5개
		check['a' - 'a'] = true;
		check['n' - 'a'] = true;
		check['t' - 'a'] = true;
		check['i' - 'a'] = true;
		check['c' - 'a'] = true;

		// 앞 anta 뒤 tica를 제외한 문자열을 갖고온다.
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			s[i] = temp.substring(4, temp.length() - 4);
		}

		dfs(0, 0);
		System.out.println(maxValue);
	}

	private static void dfs(int count, int start) {
		// basecase
		if (count == K - 5) {
			int temp = 0;
			for (int i = 0; i < N; i++) {
				boolean flag = true;

				// 배운 알파벳이 있는지 check
				for (int j = 0; j < s[i].length(); j++) {
					if (!check[s[i].charAt(j) - 'a']) {
						flag = false;
						break;
					}
				}

				if (flag) 
					temp++;				
			}
			maxValue = Math.max(temp, maxValue);
			return;
		}

		for (int i = start; i < 26; i++) {
			if (!check[i]) {
				check[i] = true;
				dfs(count + 1, i);
				check[i] = false;
			}
		}
	}
}