-
반응형
https://www.acmicpc.net/problem/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(); } }
반응형'문제풀이 > 백준oj' 카테고리의 다른 글
[백준OJ] 15681번 트리와 쿼리 - Java (0) 2023.01.02 [백준OJ] 19542번 전단지 돌리기 - Java (0) 2023.01.02 [백준OJ] 16973번 직사각형 탈출 - Java (0) 2022.12.31 [백준OJ] 16985번 Maaaaaaaaaze - Java (0) 2022.12.31 [백준OJ] 18511번 큰 수 구성하기 - Java (0) 2022.12.28 댓글