[JAVA]백준 22251: 빌런 호석

백준 22251: 빌런 호석

Link: https://www.acmicpc.net/problem/22251

풀이

• 디스플레이를 어떻게 표현할지 파악하는게 중요했던 문제.
• 필자의 경우 각 LED를 이진으로 표현하여 풀이했다.
• 각 디스플레이는 7개의 LED 상태로 표현된다.
  • 위에서부터 왼쪽, 오른쪽의 순서대로 표현한다면 0의 경우 1110111로 표현할 수 있다.
  • 마찬가지로 다른 모든 수를 이진수로 변환하고 이를 다시 10진수로 변환하여 배열에 저장한다.
• 1부터 N번째 층까지 순회하며 각 층을 표현하기 위해 바꿔야 하는 자릿수를 카운트.
  • 해당 값이 P보다 작다면 호석이가 바꿀 수 있는 경우이므로 ans 값 ++

package algorithm2024.sep.day22;

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

public class BOJ_22251_빌런호석_bit {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, K, P, X;

    static int[] nums = {119, 18, 93, 91, 58, 107, 111, 82, 127, 123};


    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());


//        X를 숫자의 배열로 변경
        int[] floor = new int[K];
        for (int i = 0; i < K; i++) {
            floor[i] = X%(int)Math.pow(10, K-i)/(int)Math.pow(10, K-1-i);
        }

        int ans =0 ;
        for (int i = 1; i <= N; i++) {
//            각 자리별로 숫자들과 비교해보고 바꿔야 하는 LED 수가 P이하라면 카운트.
            if (i == X) continue;
            int cnt = 0;
            int idx = 0;
//            첫번째 자릿수부터 변경해야 하는 횟수 카운트
            for (int j = (int) Math.pow(10, K-1); j > 0; j/=10) {
                int n = i%(j*10)/j;
                cnt+=Integer.bitCount(nums[n]^nums[floor[idx]]);
                idx++;
            }
            if(cnt<=P) ans++;
        }
        System.out.println(ans);
    }
}

---

Issue

• 초기 풀이는 비트로 하지 않았다. 비트를 단순 boolean 값으로 저장한 후 자릿수마다 7번의 순회를 통해 각 비트를 비교하는 방법을 사용.
• 비트를 다루는 문제를 안 푼지 오래 되다 보니 비효율적인 방법으로 풀이함.
• 이를 깨닫고 비트로 풀이를 다시 한 케이스.
• 아래는 boolean 배열 풀이

package algorithm2024.sep.day22;

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

public class BOJ_22251_빌런호석 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, K, P;
    static String X;

    static boolean[][] nums = {
            {true, true, true, false, true, true, true},
            {false, false, true, false, false, true, false},
            {true, false, true, true, true, false, true},
            {true, false, true, true, false, true, true},
            {false, true, true, true, false, true, false},
            {true, true, false, true, false, true, true},
            {true, true, false, true, true, true, true},
            {true, false, true, false, false, true, false},
            {true, true, true, true, true, true, true, true},
            {true, true, true, true, false, true, true}
    };


    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        X = st.nextToken();

//        X의 앞자리에 0을 채워주는 작업
        while(X.length()<K){
            X = new StringBuilder("0").append(X).toString();
        }

//        X를 숫자의 배열로 변경
        int[] floor = new int[K];
        for (int i = 0; i < X.length(); i++) {
            floor[i] = X.charAt(i) - '0';
        }

        int ans =0 ;
        for (int i = 1; i <= N; i++) {
//            각 자리별로 숫자들과 비교해보고 바꿔야 하는 LED 수가 P이하라면 카운트.
            if (i == Integer.parseInt(X)) continue;
            int cnt = 0;
            int idx = 0;
//            첫번째 자릿수부터 변경해야 하는 횟수 카운트
            for (int j = (int) Math.pow(10, K-1); j > 0; j/=10) {
                int n = i%(j*10)/j;
                for (int k = 0; k < 7; k++) {
                    if(nums[n][k]!=nums[floor[idx]][k])cnt++;
                }
                idx++;
            }
            if(cnt<=P) ans++;
        }
        System.out.println(ans);
    }
}