[Java] 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 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

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

문제 풀이

모수가 많아서 시간 초과가 날거 같지만 사실 잘 생각해보면 인원이 33명 이상이 되는 순간 같은 mbti를 가진 사람이 3명이 상이 된다. 즉 심리적인 거리가 0이된다. if문으로 n > 32 인경우는 그냥 0으로 처리해주고 32명 이하인 경우만 반복문으로 돌리면 된다.

자바 코드

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

public class N20529 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            String[] mbtis = br.readLine().split(" ");

            // 인원 수가 33명이 넘어가면 같은 MBTI를 가진 사람이 3명 이상 나올 수 밖에 없다.
            // 즉 거리는 0이다.
            if(n > 32) {
                System.out.println(0);
                continue;
            }

            int result = Integer.MAX_VALUE;
            for(int p1 = 0; p1 < n; p1++){
                for(int p2 = p1 + 1; p2 < n; p2++){
                    for(int p3 = p2 + 1; p3 < n; p3++){
                        // 사람의 심리적 거리 합을 저장할 변수
                        int cnt = 0;

                        // 각 사람끼리의 거리 합을 더한다.
                        cnt += getDistance(mbtis[p1], mbtis[p2]);
                        cnt += getDistance(mbtis[p1], mbtis[p3]);
                        cnt += getDistance(mbtis[p2], mbtis[p3]);

                        // 이전에 기록된 거리 합과 비교하여 작은 값을 저장한다.
                        result = Math.min(result, cnt);

                        // 거리 합이 0이라면 더이상 찾을 이유가 없다 for문 종료
                        if(result == 0)
                            break;
                    }
                    if(result == 0)
                        break;
                }
                if(result == 0)
                    break;
            }

            System.out.println(result);
        }
    }

    public static int getDistance(String p1, String p2){
        // 각 자리를 비교하여 다를 때마다 +1해나간다.
        // 이후 다른 자리 값의 수를 출력한다.
        int distance = 0;
        for(int i = 0; i < 4; i++){
            if(!(p1.charAt(i) == p2.charAt(i)))
                distance++;
        }

        return distance;
    }
}