[백준] 1062: 하늘에서 별똥별이 빗발친다 - JAVA

13 Nov 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

배운 알파벳을 체크하기 위해 비트마스킹을 이용했다.

알파벳은 26자인데 int자료형은 2의 31제곱까지 표현이 가능하므로 비트마스킹을 적용할 수 있다.

a, n, t, i, c 5개 문자를 -97 해서 숫자로 바꾼 뒤 체크해주었다.

K개의 글자를 배울 수 있으므로 조합을 통해 K개를 채워주었다.

K개가 되었다면 주어진 단어 중 읽을 수 있는 단어를 카운트해줬다.

---

메모리: 15216KB

시간: 300ms

언어: Java 11

코드

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

public class Main {

    static int N, K, ans;
    static String[] arr;

    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());

        arr = new String[N];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine();
        }

        int check = 0;
        check += 1 << ('a' - 97);
        check += 1 << ('n' - 97);
        check += 1 << ('t' - 97);
        check += 1 << ('i' - 97);
        check += 1 << ('c' - 97);

        ans = 0;
        if (K == 26) {
            ans = N;
        } else if (K >= 5) {
            combi(check, 0);
        }

        System.out.println(ans);
    }

    private static void combi(int check, int idx) {
        if (Integer.bitCount(check) == K) {
            countReadable(check);
            return;
        }

        for (int i = idx; i < 26; i++) {
            if ((check & (1 << i)) == 0) {
                combi(check + (1 << i), i + 1);
            }
        }
    }

    private static void countReadable(int check) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            boolean flag = true;
            for (int j = 4; j < arr[i].length() - 4; j++) {
                if ((check & (1 << arr[i].charAt(j) - 97)) == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cnt++;
            }
        }

        ans = Math.max(ans, cnt);
    }
}