#2160 : 그림 비교

풀이방법

사용된 것:

브루트포스 알고리즘

 

2022.05.10

다 비교하면 된다.

 

알고리즘은 다음과 같다.

 

일단 그림 정보를 읽어온다.

그림의 색이 두 가지 뿐이므로 boolean 배열로 저장했다.

 

그 다음 비교를 한다. 필요한 변수는 min, a, b이다.

int형 변수 min을 선언하고, 35보다 큰 수로 초기화한다.

정답에 해당하는 두 그림의 번호를 저장할 int형 변수 a와 b를 선언하고, 음수로 초기화한다.

 

그리고 가능한 모든 쌍에 대하여 다음의 과정을 반복한다.

 

두 그림을 선택한다.

두 그림을 비교하여, 서로 다른 칸의 개수를 센다.

서로 다른 칸의 개수를 담은 변수를 temp라 하겠다.

min과 temp를 비교한다.

min보다 temp가 작다면 min의 값을 temp로 업데이트하고, 방금 센 두 그림의 번호를 a와 b에 저장해둔다.

 

이러한 과정을 가능한 모든 쌍에 대하여 수행한 뒤에 a와 b에 저장되어있는 값이 정답이다.

 

점검을 모두 끝냈는데도 min의 값이 35보다 크거나 a 또는 b가 음수라면 코드가 잘못된 것이므로 고쳐야 한다.

 

아래의 정답 코드에서는 그림들의 ArrayList 상의 인덱스를 a와 b에 저장하였다. 그런데 인덱스는 그림의 번호보다 값이 1 작으므로 출력할 때 1을 더해주었다.

 

 

 

코드

Java(2022.05.10)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<boolean[][]> pics = new ArrayList<boolean[][]>();
		
		//n개의 그림 읽어오기
		for(int i = 0; i<n; i++) {
			pics.add(new boolean[5][7]);
			for(int j = 0; j<5; j++) {
				char[] input = br.readLine().toCharArray();
				 for(int k = 0; k<7; k++) {
					 if(input[k]=='.') pics.get(i)[j][k] = false;
					 else pics.get(i)[j][k] = true;
				 }
			}
		}
		
		//그림끼리 비교하기
		//정답번호를 a, b에 저장할 것임
		int a = -1;
		int b = -1;
		//가장 적은 차이가 저장될 변수 min
		int min = 40;
		//모든 그림에 대하여,
		for(int i = 0; i<n; i++) {
			//자신보다 뒷 순서인 그림들과 일일이 비교
			for(int j = i+1; j<n; j++) {
				int temp = 0;
				for(int x = 0; x<5; x++) {
					for(int y = 0; y<7; y++) if(pics.get(i)[x][y] != pics.get(j)[x][y]) temp++;
					if(temp>min) break;	//temp가 min보다 커지면 정답일 가능성이 사라지므로 즉시 넘어가기
				}
				if(min>temp) {
					a = i; b = j; min = temp;
				}
			}
		}
		
		//정답 출력
		System.out.print((a+1) + " " + (b+1));
	}

}