[백준] 1062번 : 가르침

문제

www.acmicpc.net/problem/1062

1062번: 가르침

문제해결방법

무조건 들어가는 문자열은 제거하고 나머지 문자열들을 조합해서 만족하는 개수를 확인한다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main1062_가르침 {
    
    public static int N, K, answer;
    public static boolean[] v = new boolean[26];
    public static String[] s;
    
    public static void init() {
        v['a'-'a'] = true;
        v['n'-'a'] = true;
        v['t'-'a'] = true;
        v['c'-'a'] = true;
        v['i'-'a'] = true;
    }
    
    public static int getWordCount() {
        int word = N;
        for(int i=0; i<N; i++) {
            for(int j=4; j<s[i].length()-4; j++) {
                if(!v[s[i].charAt(j)-'a']) {
                    word--;
                    break;
                }
            }
        }
        return word;
    }
    
    public static void comb(int before, int count, int k, char[] letter) {
        if(count>=k) {
            int word = getWordCount();
            if(answer<word) answer=word;
            return;
        }
        
        for(int i=before+1; i<letter.length; i++) {
            if(!v[letter[i]-'a']) {
                v[letter[i]-'a'] = true;
                comb(i, count+1, k, letter);
                v[letter[i]-'a'] = false;
            }
        }
    }
    
    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());
        s = new String[N];
        for(int i=0; i<N; i++) s[i] = br.readLine();
        Set<Character> set = new HashSet<Character>();
        init();
        answer = 0;
        if(K>=5) {
            for(int i=0; i<N; i++) {
                for(int j=4; j<s[i].length()-4; j++) {
                    char ch = s[i].charAt(j); 
                    if(!v[s[i].charAt(j)-'a'] && !set.contains(ch)) set.add(ch);
                }
            }
            if(set.size()<K-5) answer = N;
            else {
                char[] letter = new char[set.size()];
                int index = 0;
                for(char key : set) letter[index++] = key;
                comb(-1, 0, K-5, letter);
            }
        }
        System.out.println(answer);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.