[백준 알고리즘] 20529번: 가장 가까운 세 사람의 심리적 거리 (JAVA)

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

20529번: 가장 가까운 세 사람의 심리적 거리

 

---

소스코드

package Baekjoon.브루트포스;
import java.util.*;
import java.io.*;

class P20529 {
    static int bt;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());
			String[] arr = new String[N];
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int min_v = Integer.MAX_VALUE;
			
			for (int n = 0; n<N;n++) {
				arr[n] =  st.nextToken();
			}
			
			if (N > 32) { // 같은 mbti가 하나라도 3개 이상 있을 시, 답은 무조건 0임 
				sb.append(0).append("\n");
				continue;
			}
		
			else {
				for (int i=0; i<N-2;i++) {
					for (int j=i+1;j<N-1;j++) {
						for (int k=j+1; k<N; k++) {
							bt = 0;
							compare(arr[i],arr[j]);
							compare(arr[j],arr[k]);
							compare(arr[i],arr[k]);
							
							if (bt < min_v) {
								min_v = bt;
							} 
						}		
					}
				}
				sb.append(min_v).append("\n");
			}
		}	
		System.out.println(sb);
	}
	
	public static void compare(String x, String y) {
		for (int i=0; i<4;i++) {
			if (x.charAt(i) != y.charAt(i)) {
				bt += 1;
			}
		}
	}
}

 

---

풀이

★ 삼중 for문을 사용하면서 완탐으로 풀어도 되는 문제인지 긴가민가했습니다. 하지만  n이 32 초과일 경우엔 답이 0이 되고, 더이상의 반복문을 수행하지 않아도 되기에 괜찮습니다 !! 

 

★ n이 32를 초과할 때 답이 0이 되는 이유는 다음과 같습니다. mbti는 총 2^4개로 16개가 있습니다. 입력에 같은 mbti가 2개까지만 들어온다면 이는 반복문을 통해 심리적 거리가 최소가 되는 경우를 찾아줘야 합니다. 하지만 32를 넘어가는 순간, 특정 mbti가 3개 들어왔다는 것을 알 수 있습니다. 특정  mbti가 3개일 경우 심리적 거리의 최소는 항상 0이기 때문에 답에 0을 저장하고 반복문을 빠져나와도 괜찮은 것입니다. (이는 예제 2번을 보면 더 잘 이해할 수 있습니다 ! )