[백준OJ] 2160번 그림 비교 - Java

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

2160번: 그림 비교

---

 

풀이

5*7 사이즈의 격자판이 최대 50개이기 때문에 모든 그림을 하나하나 비교해도 시간초과가 나지 않을것입니다.

하지만 5*7사이즈의 격자판을 비교하는 시간을 줄이기 위해 비트연산자 XOR을 이용했습니다.

 

예를들어

..X....
.XXX...
.XX....
.....X.
.X...X.

와 같은 격자판을 일자로 늘려

..X.....XXX....XX.........X..X...X.

로 만든 뒤, X = 0, '.' = 1로 치환합니다.

11011111000111100111111111011011101

 

그림을 모두 BIT로 치환한 뒤, 각각의 그림을 모두 XOR 연산을 이용하여 비교하며 서로 다른부분이 몇개인지 도출해내며 답을 갱신하면 됩니다.

 

시간복잡도

O(N*N)

 

코드

import java.io.*;

public class Main {
    public static int getBitCount(long diff){
        int ret = 0;
        while(diff>0){
            if(diff%2==1) ret++;
            diff/=2;
        }
        return ret;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.valueOf(br.readLine());

        long[] arr = new long[n];

        for(int i=0;i<n;i++){
            long number=0;
            for(int x=0;x<5;x++){
                String line = br.readLine();
                for(char c : line.toCharArray()){
                    number<<=1;
                    if(c=='.'){
                        number+=1;
                    }
                }
            }
            arr[i]=number;
        }

        int diffCount = Integer.MAX_VALUE;
        int answer1=0;
        int answer2=0;

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                long diff = arr[i]^arr[j];
                int bitCount = getBitCount(diff);
                if(bitCount < diffCount){
                    diffCount=bitCount;

                    answer1 = i+1;
                    answer2 = j+1;
                }
            }
        }

        sb.append(answer1+" "+answer2);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
    }
}