[devmoon]백준 1062 골드4 - (Java) 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

1. 유형

백트래킹, 조합

 

2. 시뮬레이션

 

1. 26개 알파벳으로 K개의 조합 구함
2. 만든 조합으로 문자열을 만들수 있는지 체크

위의 예시처럼 'a' 't' 'n' 'c' 'i'는 처음부터 들어있기 때문에 신경쓸 필요가 없다.

따라서 파란색칸만 중복확인을 하면 된다.

 

필요한 지식

조합구하기 -> 재귀사용

중복체크 -> 비트마스크 / HashSet / 26크기의 배열 사용

가운데 문자열만 슬라이싱 방법 -> 문자열.substring()

 

겪었던 오류

 

3. 코드

1) 비트마스크 풀이

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

public class Main {
	static String str[];
	static int N, M, Len, answer;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		str = new String[N];
		answer = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			str[i] = st.nextToken();
		}
		Len = M - 5;
		int visited = 0;
		visited |= 1 << ('a' - 'a');
		visited |= 1 << ('n' - 'a');
		visited |= 1 << ('t' - 'a');
		visited |= 1 << ('c' - 'a');
		visited |= 1 << ('i' - 'a');
		if (M < 5)
			answer = 0;
		else
			comb(0, visited, 0);
		System.out.println(answer);
	}

	static void comb(int dep, int visited, int start) {
		if (dep == Len) {
			isValid(visited);
			return;
		}
		for (int i = start; i < 26; i++) {
			if ((visited & 1 << i) == 0) {
				comb(dep + 1, visited | 1<<i, i+1);
			}
		}
	}

	static void isValid(int visited) {
		int ret = 0;
		boolean stop;
		for (String s : str) {
			int start = 4;
			int end = s.length() - start;
			stop = false;
			if (start != end) {
				char[] ch = s.substring(start, end).toCharArray();
				for (char c : ch) {
					int index = c- 'a';
					if ((visited & 1 << index) == 0) {
						stop = true;
						break;
					}
				}
			}
			if (!stop) {
				ret++;
			}
		}
		answer = Math.max(ret, answer);
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

2) HashSet 풀이

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

public class Main {
	static String str[];
	static int N, M, Len, answer;
	static Set<Character> set;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		str = new String[N];
		answer = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			str[i] = st.nextToken();
		}
		Len = M - 5;
		
		set = new HashSet<>();
		set.add('a');
		set.add('n');
		set.add('t');
		set.add('i');
		set.add('c');
		if(M < 5)
			answer = 0;
		else
			comb(0, 0);
		System.out.println(answer);
	}

	static void comb(int dep, int start) {
		if(dep == Len) {
			isValid();
			return;
		}
		for(int i=start; i<26; i++) {
			char c = (char)((int)'a'+i);
			if(!set.contains(c)) {
				set.add(c);
				comb(dep+1, i+1);
				set.remove(c);
			}
		}
	}
	static void isValid() {
		int ret = 0;
		for(int i=0; i<N; i++) {
			int start = 4;
			int end = str[i].length()-4;
			boolean stop = false;
			if(start!=end) {
				char ch[] = str[i].substring(start, end).toCharArray();
				for(int j=0; j<ch.length; j++) {
					if(!set.contains(ch[j])) {
						stop=true;
						break;
					}
				}
			}
			if(!stop) {
				ret++;
			}
		}
		answer = Math.max(ret, answer);
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

비트마스크 풀이가 좀더 빠르다

 

4. 느낀점

비트마스크 복습