[boj] 1062 가르침 java

문제 풀이 방식

• 딕셔너리/hashmap 써서 문자열 카운트 제일 높은것 부터 K개 뽑아내서 출력하도록 만들어주면 될 것 같다.
• K 조건 따른 분류
  • 'a', 'n', 't', 'i', 'c' 5개 문자는 무조건 포함
  • 사용된 문자 수가 5개 이하면 단어 못배운다 -> 0개 리턴
  • K가 26이면 전부 표현가능 (N 리턴)
  • 모든 사용된 문자 수가 K-5보다 작으면 전부 표현가능 (N 리턴)
• 시간 제한 빡빡할 것 같으니 visited bool 배열 사용해서 방문 여부를 저장해 DFS 사용

문제 풀이 (Java)

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.HashMap;  
import java.util.HashSet;  
import java.util.List;  
import java.util.Scanner;  
  
public class Main {  
    static String[] info;  
    static int n;  
    static int k;  
    static ArrayList<Character> ary = new ArrayList<>();  
    static HashMap<Character, Boolean> visit;  
    static HashSet<Character> set = new HashSet<>();  
    static List<Character> list;  
    static int res = 0;  
  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        n = sc.nextInt();  
        k = sc.nextInt();  
        info = new String[n];  
        String basic = "antic";  
        visit = new HashMap<>();  
        for (int i = 0; i < basic.length(); i++) {  
            visit.put(basic.charAt(i), true);  
        }  
        for (int i = 0; i < n; i++) {  
            String temp = sc.next();  
            info[i] = temp;  
            for (int j = 4; j < temp.length() - 4; j++) {  
                if (!visit.containsKey(temp.charAt(j))) {  
                    set.add(temp.charAt(j));  
                }  
  
            }  
        }  
        list = new ArrayList<>(set);  
        if (k - 5 > list.size()) {  
            res = n;  
        } else {  
            dfs(0, 0);  
        }  
        System.out.println(res);  
  
    }  
  
    static void dfs(int index, int count) {  
        if (count == k - 5) {  
            int currRes = 0;  
            extracted(currRes);  
            return;  
        }  
        if (index >= list.size()) {  
            return;  
        }  
  
        visit.put(list.get(index), true);  
        dfs(index + 1, count + 1);  
        visit.put(list.get(index), false);  
        dfs(index + 1, count);  
  
    }  
  
    static void extracted(int currRes) {  
        for (int i = 0; i < n; i++) {  
            Boolean isTrue = true;  
            String temp = info[i];  
            for (int j = 4; j < info[i].length() - 4; j++) {  
                if (visit.containsKey(temp.charAt(j)) && !visit.get(temp.charAt(j))) {  
                    isTrue = false;  
                    break;  
                } else if (!visit.containsKey(temp.charAt(j))) {  
                    isTrue = false;  
                    break;  
                }  
            }  
            if (isTrue) {  
                currRes++;  
            }  
            if (currRes > res) {  
                res = currRes;  
            }  
        }  
    }  
  
}