[BOJ/Java] 20529. 가장 가까운 세 사람의 심리적 거리

[BOJ/Java] 20529. 가장 가까운 세 사람의 심리적 거리

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

---

문제 해석

이 문제는 N명의 사람들의 MBTI를 입력 받아서 가장 심리적 거리가 가까운 세 사람의 거리를 찾는 문제이다. MBTI 간의 거리는 각 자리마다 다른 문자일 때마다 거리가 1씩 증가한다. 예를 들어, MBTI가 'INTJ', 'ENTJ'인 경우 거리는 1이다.

풀이 과정

• 비둘기집 원리 활용: N이 33 이상일 경우, 비둘기집 원리에 의해 반드시 최소한 하나의 MBTI가 중복되어 거리가 0인 세 사람을 찾을 수 있다.
• MBTI 거리 계산: 세 MBTI 사이의 거리를 계산하는 함수를 통해 심리적 거리를 계산한다.
• 브루트포스 접근: N이 32 이하일 때, 모든 가능한 세 사람의 조합에 대해 거리를 계산하여 최소 거리를 찾는다.

코드

package edu.ssafy.im.BOJ.Silver.S1.No20529;

import java.io.*;

public class Main {
	private static int T;  // 테스트 케이스 수
	private static int N;  // 참가자 수

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());  // 테스트 케이스 수 입력 받기
		for (int t = 0; t < T; t++) {
			N = Integer.parseInt(br.readLine());  // 참가자 수 입력 받기
			st = new StringTokenizer(br.readLine());  // MBTI 입력

			// 비둘기집 원리에 의해 33명 이상일 경우, 거리 0이 확정
			if (N > 32) {
				sb.append(0).append("\n");
				continue;
			}

			String[] mbti = new String[N];
			for (int i = 0; i < N; i++) {
				mbti[i] = st.nextToken();  // MBTI 데이터 저장
			}

			int ans = Integer.MAX_VALUE;  // 최소 거리 초기화
			L: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++) {
						int sum = 0;
						for (int l = 0; l < 4; l++) {
							if (mbti[i].charAt(l) != mbti[j].charAt(l)) sum++;
							if (mbti[j].charAt(l) != mbti[k].charAt(l)) sum++;
							if (mbti[k].charAt(l) != mbti[i].charAt(l)) sum++;
						}
						ans = Math.min(ans, sum);
						if (ans == 0) break L;  // 최소값이 0이면 즉시 반복 중단
					}
				}
			}
			sb.append(ans).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

시간 복잡도 분석

최악의 경우, 모든 조합을 확인해야 하므로, 𝑁명 중 3명을 고르는 조합의 수는 𝑂(𝑁^3)이다. 𝑁의 최댓값이 32이므로, 이 경우 최대 연산 수는 32,768번이 될 수 있다.

느낀점

이 문제는 복잡한 입력 조건과 비둘기집 원리를 활용하여 효율적으로 해결하는 방법을 배울 수 있었다. 문제를 단순화하는 논리적 사고와 최적화 기법을 적용해야 하는 좋은 예시이며, MBTI 간 거리를 계산하는 문제는 효율적인 알고리즘 설계를 요구한다.