BOJ_1062 : 가르침

👉 문제링크

---

---

🔸 문제 분석 🔸

• K개의 문자를 배웠을 때, N개의 단어(문자열) 중 최대 몇 개를 읽을 수 있는지 출력한다.
• 모든 단어는 anta로 시작해 tica로 끝난다.

🔸 문제 풀이 🔸

• 단어의 시작과 끝이 정해져 있으므로, 'a', 'n', 't', 'i', 'c' 다섯 글자는 반드시 읽을 줄 알아야 한다.
  • K가 5 미만인 경우에는 0을 반환한다.
• K >= 5 일 때, K-5 개의 문자를 추가로 배워서 몇 개의 단어를 읽을 수 있는지 확인해야 한다.
  • 비트 마스킹으로 배운 문자를 표시한다.
  • 배운 문자로 단어를 읽을 수 있는지 비트 마스킹으로 확인한다.

🔸 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int N, K, MAX;
    private static int[] usedChar;

    public static void main(String[] args) throws IOException {
        // Intput
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        usedChar = new int[N];
        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();
            for (char c : chars) {
                usedChar[i] |= (1 << c - 'a'); // 사용 된 문자 비트마스킹 : 1
            }
        }

        // a, c, i, n, t 는 반드시 읽을 줄 알아야 함
        if (K < 5) {
            bw.write("0");
            bw.flush();
            return;
        }

        int mustLearned = (1 << ('a' - 'a')) | (1 << ('c' - 'a')) | (1 << ('i' - 'a')) | (1 << ('n' - 'a')) | (1 << ('t' - 'a'));


        // Combination : K개의 문자 선택 후 읽을 수 있는 단어 수 체크
        MAX = 0;
        combination(0, mustLearned, 5);

        // Output
        bw.write(Integer.toString(MAX));
        bw.flush();
    }

    private static void combination(int start, int learned, int cnt) {
        if (cnt == K) { // K개의 문자를 골랐으면 읽을 수 있는 단어 수 확인
            MAX = Math.max(MAX, read(learned));
            return;
        }
        for (int i = start; i < 26; i++) { // 비트 마스킹 하나씩 1 만들어보기

            if ((learned & (1 << i)) == 0) { // 안배운 문자 배우기
                combination(i + 1, learned | (1 << i), cnt + 1);
            }
        }
    }

    private static int read(int learned) { // 읽을 수 있는 단어 수 세기
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if ((usedChar[i] & learned) == usedChar[i])
                cnt++;
        }
        return cnt;
    }
}

🔸 코드 해석 🔸

• 읽을 단어들에 사용된 문자를 usedChar 배열에 비트 마스킹한다.
• K가 5 미만이면 읽을 수 있는 단어가 없으므로 0을 출력하고 프로그램을 종료한다.
• 반드시 읽을 줄 알아야 하는 5개의 단어를 mustLearned에 비트 마스킹한다.
• 재귀 메서드 combination으로 조합 형식을 통해 추가적으로 배울 문자를 하나씩 선택해보고, 읽을 수 있는 단어의 최대값 MAX를 구한다.
  • K개의 문자를 모두 배웠으면 read 메서드에서 읽을 수 있는 단어의 수를 구한다.
  • 배울 문자를 선택할 때 start로 경우의 수가 겹치지 않도록 하고, 비트가 0인지 확인해서 현재 배우지 않은 문자면 배워본다.
• MAX를 출력한다.

---

🔸 end 🔸

•  처음엔 시간이 1초로 짧길래 Greedy로 풀이해야하는 줄 알고, 가장 많이 사용된 문자 순으로 배우고자 했다.
  • 하지만 반례가 있었고, 모든 경우의 수를 살펴봐야하는 Brute Force 문제여서 틀렸다.
  • 태그에 비트 마스킹이 있어서, 조합으로 풀이해보고자 했지만 시간 초과가 났다. 알고보니 문제에 단어 앞뒤 문자는 고정되어 있다는 걸 못봤었다...
• 오랜만에 조합을 사용해서 많이 미숙한 점이 있었다.
  • combination 메서드의 형태는 아주 고정적으로 start와 현재값, cnt 가 들어가는데 형태를 떠올리는데 오래걸렸던 것 같다.
  • 또 비트마스킹을 많이 활용해보지 않아서 활용성이 좋지 않았던 것 같다. cnt를 인자로 안넘기고 Integer.bitCount()메서드로 learned를 확인해 보는 방법도 괜찮은 것 같다.
• 드디어 solved.ac 프로필 의 풀이한 100문제 모두 골드4 이상으로 맞췄다.
  • 앞으로는 골드3 이상의 문제를 스트릭으로 풀어야한다.
  • 아직 미숙한 부분이 많지만 열심히 해보자!