BOJ#1062 가르침

BOJ#1062 가르침

* 문제

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

* 풀이

꽤 어렵게 푼 문제입니다. 이 문제는 주어진 단어들을 어떤 자료구조에 담는지가 핵심인 것 같습니다.

1. 단어를 읽을 수 있다는 것은 그 단어를 이루고 있는 알파벳을 모두 알고 있다는 것입니다.

-> 따라서 단어를 입력 받을 때, 불필요한 정보는 받지 말고 각 단어를 이루고 있는 알파벳의 모음으로 입력을 받습니다.

-> 즉 antahellotica 단어는  [a, n, t, h, e, l, o, i, c] 으로 입력을 받으면 됩니다.

-> 처음에는 중복되는 알파벳은 받지 않고 순서는 상관 없으므로 HashSet을 이용하려 했지만 재귀 형태에서 iteration을 사용하는 것에 불편함이 있어서 , 조금 더 편하고 빠른 방법으로 bit mask를 이용해 보았습니다.

2. 다음으로는 [a~z] 알파벳 중에 k개를 배우는 것입니다.

-> 26개 중에 k개를 순서 없이 뽑는 조합 문제로 생각할 수 있겠습니다.

---

* 나의 코드

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

/**
 * BOJ#1062 가르침
 * https://www.acmicpc.net/problem/1062
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int N; // 단어의 수
        int K; // 가르칠 글자의 수
        int[] word;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        word = new int[N];

        // 입력받는 String -> char[] -> 중복없이 int로 저장
        for (int i = 0; i < N; i++) {

            char[] tempStr = br.readLine().toCharArray();

            for (char x : tempStr) {

                word[i] |= (1 << x - 'a');
            }
        }

        System.out.println(solve(0, K, 0, word));
    }

    static int solve(int alphabetIdx, int K, int mask, int[] word) {

        // 재귀 종료 조건
        if (K < 0) {

            return 0;
        }

        // 재귀 종료 조건 : 알파벳 범위를 넘은 경우(끝까지 진행한 경우 검사)
        if (alphabetIdx == 26) {

            int cnt = 0;
            for (int i = 0; i < word.length; i++) {

                if (word[i] == (word[i] & mask)) {

                    cnt++;
                }
            }

            return cnt;
        }

        int ans = 0;
        int case1, case2;

        // 1. 해당 알파벳을 배우는 경우
        case1 = solve(alphabetIdx + 1, K - 1, mask | (1 << alphabetIdx), word);
        case2 = 0;

        // 2. 해당 알파벳을 배우지 않는 경우
        switch (alphabetIdx) {

            case 'a' - 'a':
            case 'n' - 'a':
            case 't' - 'a':
            case 'i' - 'a':
            case 'c' - 'a':
                break;

            default:

                case2 = solve(alphabetIdx + 1, K, mask, word);
                break;
        }

        ans = Math.max(case1, case2);

        return ans;

    }
}