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

 

 

문제

여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가?

MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과)

MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다.

외향(E) / 내향(I)
감각(S) / 직관(N)
사고(T) / 감정(F)
판단(J) / 인식(P)

각 척도마다 두 가지 분류가 존재하므로, MBTI는 총
$2^4 = 16$가지 유형이 있음을 알 수 있다. 일반적으로 MBTI의 유형들은 각 분류를 나타내는 알파벳 한 글자씩을 따 네 글자로 표시하게 된다. 모든 유형의 목록은 다음과 같다.

ISTJ, ISFJ, INFJ, INTJ, ISTP, ISFP, INFP, INTP, ESTP, ESFP, ENFP, ENTP, ESTJ, ESFJ, ENFJ, ENTJ
MBTI 성격 유형을 이용하면 두 사람 사이의 심리적인 거리를 정의할 수 있다. 이는 두 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수로 정의된다. 예를 들어, MBTI 유형이 ISTJ인 사람과 ISFJ인 사람 사이의 거리는 1이며,

INTP인 사람과 ENTJ인 사람 사이의 거리는 2이다.

이 정의를 확장해서 세 사람 사이의 심리적인 거리도 정의할 수 있다. 세 사람
$A, B, C$가 있을 때 이들의 심리적인 거리는

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

로 정의한다.

대학교에서 심리학 교수로 일하는 종서는 자신이 가르치는 학생들의 심리적인 특성을 분석하고 싶어한다.

오늘이 생일인 종서를 위해
$N$명의 학생들의 MBTI 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.

풀이

우선 전체적인 탐색을 모두 진행해야 한다.
배열을 받아서 3명을 뽑아야 하니 조합을 이용하여 구현하기로 하였다.
이후 각 3가지 MBTI에 대해서 charAt으로 문자 하나하나의 차이 갯수를 구하였다.

조합을 재귀를 이용하여 구현하였는데, 차이의 갯수가 0이라면 이 값이 최솟 값이므로 다음 탐색을 진행할 필요가 없다.
따라서 0이면 return을 하여 재귀를 빨리 빠져나오게 하여 시간초과를 피하게 하였다.

이러한 구현말고 새로운 풀이를 보았는데 16가지의 MBTI가 각각 두명씩 균둥하게 존재한다면 인원은 32명이다.
이때 한명의 인원이 추가된다면 하나의 MBTI에 3명이 몰리게 되므로 거리의 최솟값은 무조건 0이 된다.
이러한 원리를 비둘기 집의 원리라고 하는데 이러한 원리를 이용한 풀이도 존재하였다.

import java.lang.*;
import java.io.*;
import java.util.*;

public class Main {
    static int sum;
    static String[] combine = new String[3];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            sum = Integer.MAX_VALUE;
            int N = Integer.parseInt(br.readLine());
            combine = new String[3];

            String[] arr = br.readLine().split(" ");
            collect(arr, 0, 0);
            System.out.println(sum);
        }
    }

    static void collect(String[] arr, int start, int depth) {
        if (depth == 3) {
            sum = Math.min(sum, compare(combine));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            combine[depth] = arr[i];
            collect(arr, i + 1, depth + 1);
            if (sum == 0) {
                return;
            }
        }
    }

    static int compare(String[] arr) {
        int sum = 0;
        for (int i = 0; i < 4; i++) {
            if (arr[0].charAt(i) != arr[1].charAt(i)) {
                sum++;
            }

            if (arr[1].charAt(i) != arr[2].charAt(i)) {
                sum++;
            }

            if (arr[0].charAt(i) != arr[2].charAt(i)) {
                sum++;
            }
        }
        return sum;
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EA%B0%80%EC%9E%A5%20%EA%B0%80%EA%B9%8C%EC%9A%B4%20%EC%84%B8%20%EC%82%AC%EB%9E%8C%EC%9D%98%20%EC%8B%AC%EB%A6%AC%EC%A0%81%20%EA%B1%B0%EB%A6%AC%20%EC%84%B1%EA%B3%B5

Algorism/BOJ/가장 가까운 세 사람의 심리적 거리 성공 at main · Win-9/Algorism