[백준] 1062번 가르침 (Java)

백준 1062번 가르침 : https://www.acmicpc.net/problem/1062

1062번: 가르침

 

 

<가르침>은 브루트 포스, 시뮬레이션 문제이다.

입력으로 단어의 개수(N)와, 김지민이 가르치는 글자의 개수(K)가 주어진다.

문제에서 특이한 조건이 하나 있는데, 모든 단어는 "anta"로 시작되고 "tica"로 끝난다는 점이다.

따라서 a, c, i, n, t는 김지민이 필수적으로 가르쳐야 된다.

아래의 예시가 있다면 rc, hello, car에서만 추가적으로 가르칠 글자를 선택해주면 된다.

antarctica
antahellotica
antacartica

 

입력을 받으면 substring을 사용하여 앞의 "anta"와 뒤의 "tica"를 잘라준다.

그렇게 나온 [rc, hello, car] 배열을 다시 한번 가공해서 중복된 문자가 없는 [r, e, h, l, o] 리스트로 만들어준다.

여기서 r개를 골라서 체크해주면 된다. r개를 고르는 것은 조합을 사용해서 구현했다.

위의 예제에서는 5개의 후보 중에 1개를 골라 판단해주면 된다.

 

이러한 방법으로 구현하게 되면, 한 가지 예외가 생긴다.

K = 6이고, 단어가 antatica 이렇게 된다면 리스트가 생기지 않기 때문에 comb 함수의 getMin 함수가 동작하지 않는다.

즉, 가르칠 수 있는 K가 후보 리스트보다 많게 되는 경우에는 모든 단어를 가르칠 수 있게 된다.

한 번의 실패를 하고 예외처리를 해주니 바로 통과할 수 있었다.

 

통과한 후 다른 사람들의 코드를 보니 비트 마스크(Bit Mask)를 활용한 경우가 있었다.

나는 알파벳을 고를 때 boolean[26] 배열을 사용했는데,

비트 마스크를 활용하면 시간도 더 빠르고 메모리도 더 적게 사용할 수 있다.

다음에 기회가 된다면 비트 마스크를 활용해서 다시 한번 풀어봐야겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static int n, k, max = Integer.MIN_VALUE;
    static String[] word;
    static boolean[] alpha = new boolean[26];
    static ArrayList<Character> list;

    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()) - 5;
        if (k < 0) {
            System.out.println(0);
            return;
        }
        word = new String[n];
        
        for (int i = 0; i < n; i++) {
            String temp = br.readLine();
            word[i] = temp.substring(4, temp.length() - 4); // [rc, hello, car]
        }

        setAlpha(new char[]{'a', 'c', 'i', 'n', 't'});
        list = getList();  // [r, e, h, l, o]

        if(list.size() <= k) max = n;
        else comb(0,0);

        System.out.println(max);
    }

    static void comb(int start, int depth) {
        if (depth == k) {
            getMin();
            return;
        }

        for (int i = start; i < list.size(); i++) {
            char c = list.get(i);
            alpha[c - 'a'] = true;
            comb(i + 1, depth + 1);
            alpha[c - 'a'] = false;
        }
    }

    static void getMin() {
        int count = 0;
        boolean flag;

        for (int i = 0; i < n; i++) {
            flag = true;
            for (int j = 0; j < word[i].length(); j++) {
                char c = word[i].charAt(j);
                if (!alpha[c - 'a']) {
                    flag = false;
                    break;
                }
            }
            if(flag) count++;
        }
        if(max < count) max = count;
    }

    static ArrayList<Character> getList() {
        HashSet<Character> set = new HashSet<>();
        ArrayList<Character> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < word[i].length(); j++) {
                char c = word[i].charAt(j);
                if (!alpha[c - 'a']) set.add(c);
            }
        }

        result.addAll(set);
        return result;
    }

    static void setAlpha(char[] character) {
        for (char c : character) {
            alpha[c - 'a'] = true;
        }
    }
}