백준 1062번 가르침

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

1062번: 가르침

문자열 문제를 풀어보려했으나? dfs였던 문제; 비트마스킹 연습도 되어서 좋았다. (근데 그래도 코테에서는 배열 visit체크로 풀 것 같다. 더 구현이 편함..) 비트마스킹이 손에 덜 익어서 좀 어려웠던 문제.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N,K,result;
	static List <Word> words = new ArrayList<>();
	static class Word implements Comparable<Word>{
		char [] word;
		int point;
		int bit;
		Word(String s){
			word = s.toCharArray();
		}
		@Override
		public int compareTo(Word o) {
			return o.point-this.point;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		for(int n=0;n<N;n++) {
			Word w = new Word(br.readLine());
			words.add(w);
			makeBit(w);
		}
		Collections.sort(words);
		for(Word w : words) {
			if(w.point<=K) {
				result++;
			}
		}
		System.out.println(result);
	}
	static void makeBit(Word w) {
		int bit=0;
		char [] word = w.word;
		for(int i=0;i<w.word.length;i++) {
			int now = (1<<25)>>(word[i] - 'a'); // 25비트 밀어서 a부터 체크해놓고 알파벳 순서만큼 다시 오른쪽으로 밀기
			bit = bit | now; // 알파벳 체크
		}
		w.bit = bit;
		w.point = Integer.bitCount(bit);
	}

}

첫번째시도. (틀렸음)

1. 알파벳이 많이 사용된 단어 순서대로 정렬
2. 해당 단어와 다른단어들을 비교하며 탐색 -> 여기서 탐색이구나 뒤늦게 생각하고 갈아 엎었다.

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

public class bj1062 {
	static int N,K,result,bit;
	static List <char[]> words = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		if(K<5) {
			System.out.println(0);
			return;
		}
		if(K==26) {
			System.out.println(N);
			return;
		}
		//(1<<25)>>(alpha - 'a') 왼쪽부터 비트채우기
		//1<<(alpha - 'a') 오른쪽부터 채우기
		bit |= 1<<('a'-'a');
		bit |= 1<<('c'-'a');
		bit |= 1<<('i'-'a');
		bit |= 1<<('n'-'a');
		bit |= 1<<('t'-'a');
		
		for(int n=0;n<N;n++) {
			char[] word = br.readLine().toCharArray();
			words.add(word);
		}
		dfs(0,0,bit);
		System.out.println(result);
	}
	static void dfs(int index, int start,int bit) {
		if(index == K-5) { //종결조건 acint빼고 나머지
			int count = 0;
			for(char[] word : words) { //단어들
				boolean chk = true;
				for(char letter: word) { //글자들
					if((bit&1<<(letter-'a'))==0) { //1&1 = 1 나머지들
						chk = false;
						break;
					}
				}
				if(chk) count++;
			}
			result = Math.max(result, count);
			return;
		}
		
		for(int i = start;i<26;i++) {
			if((bit&1<<i)!=0) continue;
			dfs(index+1,i+1,bit | 1<<i);
		}
	}
}

두번째 시도 (정답)

1. 비트마스킹 26비트로 알파벳 체크.  원래 a부터 왼쪽비트쓰려고 했으나 코드가 조금 길어져서 오른쪽부터 밀어서 사용
2. dfs의 기본 기저조건과 나머지 분리 (이거 생각하는게 좀 걸린듯?)
3. 기저조건에서 단어돌면서 알파벳 체크
4. 아니면 브루트포스
5. K<5, K==26은 뒤늦게 추가