세 사람의 심리적 거리

문제

세 사람의 심리적 거리

문제 설명

여러분은 요즘 유행하는 심리검사인 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는 총 24=16$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
ENTJ INTP ESFJ
4
ESFP ESFP ESFP ESFP
5
INFP INFP ESTP ESTJ ISTJ | 8
0
4 |

입출력 예 설명

• 첫 번째 테스트 케이스의 경우, ENTJ와 INTP의 심리적인 거리는 2, ENTJ와 ESFJ의 심리적인 거리는 2, INTP와 ESFJ의 심리적인 거리는 4이므로 세 사람의 심리적인 거리는 $2+2+4=8$이다. 2 2 4 2+2+4=8
  
• 두 번째 테스트 케이스의 경우, 어떤 사람 둘을 골라도 심리적인 거리가 0이므로 가장 가까운 세 사람의 심리적인 거리는 0이다. 0 0
  
• 세 번째 테스트 케이스의 경우, 심리적인 거리를 최소화하려면 MBTI가 ESTP, ESTJ, ISTJ인 세 사람을 골라야 한다. ESTP와 ESTJ의 심리적인 거리는1, ESTP와 ISTJ의 심리적인 거리는 2, ESTJ와 ISTJ의 심리적인 거리는 1이므로 세 사람의 심리적인 거리는 1+2+1=4이다. 1 2 1 1+2+1=4
  

아이디어

완전 탐색 → 시간 초과

비둘기집 원리

비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다.

17명 이상이 되면 무조건 겹치는 유형 하나 이상 발생

32명 이상이 되면 무조건 셋이 겹치는 유형 하나 이상 발생

제출 코드

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

public class one20529 {
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testCnt = Integer.parseInt(reader.readLine());
        
        for (int test = 0; test < testCnt; test++) {
            int personCnt = Integer.parseInt(reader.readLine());

            String[] personMbti = new String[personCnt];
            StringTokenizer mbtiToken = new StringTokenizer(reader.readLine(), " ");

            // 입력받기
            for (int i = 0; i < personCnt; i++) {
                personMbti[i] = mbtiToken.nextToken();
            }

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

            int minDistance = Integer.MAX_VALUE;

            for (int first = 0; first < personCnt; first++) {
                for (int second = first + 1; second < personCnt; second++) {
                    for (int third = second + 1; third < personCnt; third++) {
                        int temp = 0;
                        for (int alpha = 0; alpha < 4; alpha++) {
                            temp += (personMbti[first].charAt(alpha) != personMbti[second].charAt(alpha) ? 1 : 0);
                            temp += (personMbti[second].charAt(alpha) != personMbti[third].charAt(alpha) ? 1 : 0);
                            temp += (personMbti[first].charAt(alpha) != personMbti[third].charAt(alpha) ? 1 : 0);
                        }
                        minDistance = Math.min(temp, minDistance);
                        if (minDistance == 0) break;
                    }
                }
            }
            System.out.println(minDistance);
        }
    }

    public static void main(String[] args) throws IOException {
        new one20529().solution();
    }
}