[20529] 가장 가까운 세 사람의 심리적 거리

---

문제 분석

총 16가지의 MBTI 가 있다.
해당 MBTI 로 심리적인 거리를 측정할 수 있다.

• E or I 같으면 거리는 +0, 다르면 거리는 +1
• S or N 같으면 거리는 +0, 다르면 거리는 +1
• T or F 같으면 거리는 +0, 다르면 거리는 +1
• J or P 같으면 거리는 +0, 다르면 거리는 +1

ISTJ 와 ISFJ 는 T 와 F 만 다르므로
이 사이의 심리적인 거리는 1 이 된다.

세 사람 A, B, C가 있을 때 이들의 심리적 거리는 아래의 식으로 나타낼 수 있다.

(A와 B 사이의 심리적인 거리) + (B와 C 사이의 심리적인 거리) + (A와 C 사이의 심리적인 거리)

이때, 최대 100,000 명의 MBTI 가 주어진다.
심리적 거리의 최솟값을 출력하라.

---

풀이 과정

🎯 우선 100,000명의 경우의 수까지 구할 필요가 없다.

MBTI 는 총 16개다.
만약 17개의 MBTI 가 주어진다면
분명 한 종류의 MBTI 는 2개 이상이 될 것이다.

MBTI 는 총 16개다.
만약 15개의 MBTI 가 주어진다면
한 종류의 MBTI 가 15개일 수도 있고, 각각 1개씩 있을 수도 있고, 많은 경우의 수가 존재한다.

MBTI 는 총 16개다.
만약 33개의 MBTI 가 주어진다면
분명 한 종류의 MBTI 는 3개 이상이 될 것이다.

이 원리를 비둘기집 원리라고 한다.

비둘기가 n마리,
비둘기집이 m개 있을 때 n이 m보다 크면 적어도 하나의 집에는 비둘기가 2마리 이상 들어간다는 원리

해당 원리를 이용하면 33개 이상일 경우 한 종류의 MBTI 는 3개 이상이 될 것이므로
정답인 0을 출력하고 탐색을 종료하면 된다.

if (mbtiSize > 32) {
    System.out.println("0");
    continue;
}

🎯 최소 3 <= N <= 32 경우의 수 밖에 없다. 완전 탐색을 하자.

핵심 로직이다.
2 명의 MBTI 를 비교하는 로직이다.
MBTI 는 총 4개 이므로 String 으로 받아서 하나씩 뜯은 다음 같지 않다면 거리를 +1 해주자.

private static int calDistance(String mbti1, String mbti2) {
    int distance = 0;

    if (mbti1.charAt(0) != mbti2.charAt(0)) distance++;
    if (mbti1.charAt(1) != mbti2.charAt(1)) distance++;
    if (mbti1.charAt(2) != mbti2.charAt(2)) distance++;
    if (mbti1.charAt(3) != mbti2.charAt(3)) distance++;

    return distance;
}

우리가 필요한 건 3명분이다.
위의 메서드를 호출하는 메서드로 3명의 심리적인 거리를 구하자.

private static int cal(String mtbi1, String mtbi2, String mtbi3) {
    return calDistance(mtbi1, mtbi2) + calDistance(mtbi1, mtbi3) + calDistance(mtbi2, mtbi3);
}

위의 메서드에서 필요한 MBTI 는 모두 탐색해서 하나씩 매개변수로 넘겨주면 된다.

String[] mbti = br.readLine().split(" ");

for (int j = 0; j < mbtiSize; j++) {
    for (int k = j + 1; k < mbtiSize; k++) {
        for (int l = k + 1; l < mbtiSize; l++) {
            result = Math.min(result, cal(mbti[j], mbti[k], mbti[l]));
        }
    }
}

배열에 담아서 모든 경우의 수를 탐색하자. (그래봤자 최대 32명이다.)

---

나의 생각

원리를 생각하며 탐색하지 않아도 될 범위를 줄여간다면 depth 가 많은 완전 탐색도
주어진 시간안에 해결할 수 있다.

---

코드

package baekjooncompletion;

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

public class BaekJoon20529 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int size = Integer.parseInt(br.readLine());

        for (int i = 0; i < size; i++) {
            int mbtiSize = Integer.parseInt(br.readLine());

            String[] mbti = br.readLine().split(" ");

            if (mbtiSize > 32) {
                System.out.println("0");
                continue;
            }

            int result = Integer.MAX_VALUE;

            for (int j = 0; j < mbtiSize; j++) {
                for (int k = j + 1; k < mbtiSize; k++) {
                    for (int l = k + 1; l < mbtiSize; l++) {
                        result = Math.min(result, cal(mbti[j], mbti[k], mbti[l]));
                    }
                }
            }

            System.out.println(result);
            
        }

    }

    private static int cal(String mtbi1, String mtbi2, String mtbi3) {
        return calDistance(mtbi1, mtbi2) + calDistance(mtbi1, mtbi3) + calDistance(mtbi2, mtbi3);
    }

    private static int calDistance(String mbti1, String mbti2) {
        int distance = 0;

        if (mbti1.charAt(0) != mbti2.charAt(0)) distance++;
        if (mbti1.charAt(1) != mbti2.charAt(1)) distance++;
        if (mbti1.charAt(2) != mbti2.charAt(2)) distance++;
        if (mbti1.charAt(3) != mbti2.charAt(3)) distance++;

        return distance;
    }

}