[ 백준 / 파이썬 ] 실버 1 - 20529. 가장 가까운 세 사람의 심리적 거리

난이도

문제

여러분은 요즘 유행하는 심리검사인 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 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.

입력

첫 줄에는 테스트 케이스의 수를 나타내는 정수
$T$가 주어진다.

각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 하나의 정수
$N$이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

출력

각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.

제한

• $1 \le T \le 50$ 
• $3 \le N \le 100\,000$ 
• 각 테스트 케이스의 $N$의 합은 $100\,000$을 넘지 않는다.

예제

입력	출력
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$이다.
• 두 번째 테스트 케이스의 경우, 어떤 사람 둘을 골라도 심리적인 거리가 $0$이므로 가장 가까운 세 사람의 심리적인 거리는 $0$이다.
• 세 번째 테스트 케이스의 경우, 심리적인 거리를 최소화하려면 MBTI가 ESTP, ESTJ, ISTJ인 세 사람을 골라야 한다. ESTP와 ESTJ의 심리적인 거리는 $1$, ESTP와 ISTJ의 심리적인 거리는 $2$, ESTJ와 ISTJ의 심리적인 거리는 $1$이므로 세 사람의 심리적인 거리는 $1+2+1=4$이다.

풀이

N 이 최대 10만 까지 존재 한다는 것이 함정인 문제이다.
MBTI 는 최대 16가지 조합으로 이루어지고, 최소 48명이 모이면 무조건 3사람은 같은 MBTI 를 가질 수 밖에 없다.

이러한 함정을 잘 캐치하여 문제를 해결하면 3중 반복문으로도 쉽게 해결할 수 있다.

괜히 어렵게 그래프로 생각했다..

코드

from sys import stdin
from collections import deque

input = stdin.readline


def solution():
    T = int(input())
    for _ in range(T):
        answer = 2e9
        N = int(input())
        arr = list(input().split())
        if len(arr) >= 48:
            print(0)
            continue

        for i in range(N):
            for j in range(i + 1, N):
                for k in range(j + 1, N):
                    A = arr[i]
                    B = arr[j]
                    C = arr[k]

                    distance_AB = 0
                    distance_BC = 0
                    distance_AC = 0

                    if A != B:
                        for l in range(4):
                            if A[l] != B[l]:
                                distance_AB += 1
                    if B != C:
                        for l in range(4):
                            if B[l] != C[l]:
                                distance_BC += 1

                    if A != C:
                        for l in range(4):
                            if A[l] != C[l]:
                                distance_AC += 1

                    answer = min(answer, distance_AB + distance_BC + distance_AC)

        print(answer)


solution()