[백준] 가장 가까운 세 사람의 심리적 거리 - Java

문제

여러분은 요즘 유행하는 심리검사인 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⁴=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≤T≤50
•  3≤N≤100000
• 각 테스트 케이스의 N의 합은 100000을 넘지 않는다.

예제 입력 1

3
3
ENTJ INTP ESFJ
4
ESFP ESFP ESFP ESFP
5
INFP INFP ESTP ESTJ ISTJ

예제 출력 1 

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$이므로 세 사람의 심리적인 거리는 1+2+1=4이다.

풀이 방법

• 비둘기집 원리를 이용하였다.
• 비둘기집 원리를 이용하여, 16가지만 존재하는 MBTI는 33개 이상의 입력을 받으면 반드시 어느 한 MBTI는 3개가 있음이 확실함을 알았고, 이를 이용해 N이  33 이상인 경우는 0을 출력(같은 MBTI가 3개면 심리적거리는 0이니까)하여 넘기도록 했다.

비둘기집 원리란?

• N개의 상자에 N + 1개의 물건을 넣을 때, 어느 상자에는 반드시 2개 이상의 물건이 들어간다는 원리

귀류법을 이용해 증명이 가능하다.

모든 비둘기가 비둘기집에 빠짐없이 들어가야 한다는 조건 하에서, 
n+1 마리의 비둘기와 n개의 비둘기집이 있고 한 집당 한 마리씩만 존재한다고 가정하면
(p∧∼q), 비둘기집 전체에는 최대 n 마리의 비둘기가 존재할 수 있게 되는데, 비둘기의 숫자는 
n+1 마리이기에 어느 집에도 들어가지 못한 비둘기 한 마리가 남을 수밖에 없게 되므로 가정에 
모순이 발생하게 된다. 따라서 모든 비둘기집에 한마리의 비둘기만 들어가야 한다는 제한은 성립할 수 없으며, 이에 따라 "n+1 마리의 비둘기를 n 개의 비둘기집에 넣는다면, 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 존재한다. (p→q) "가 참이 된다. 비둘기 집의 원리에 대한 문제를 구할 때에 아니면 표현할 때에는 올림 기호를 사용한다.
사람으로 치면, 다섯 명이 4개 집에 나눠 들어가면 2인 이상 가구가 최소 하나는 생긴다는 것. 사실 너무나 당연하고 직관적이어서 이게 증명씩이나 필요한지, '정리'라는 이름을 가지고 있어야 하는지 의문이 들 수도 있지만, 실제 생활에서 뿐만 아니라 많은 수학/과학, 그 중에서도 특히 조합 문제를 해결할 때 이 원리가 사용되며 이름이 없으면 불편하기 때문에 편의상 적당히 이름을 붙인 것으로 알려져 있다. '입력의 범위보다 출력의 범위가 작아 다른 입력값이어도 동일한 출력값이 나올 수 있는 상황'을 '비둘기 집의 원리'로 표현하면 간단하기 때문이다.

출처 - 
https://namu.wiki/w/%EB%B9%84%EB%91%98%EA%B8%B0%20%EC%A7%91%EC%9D%98%20%EC%9B%90%EB%A6%AC

풀이 코드

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

public class Main {

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

		for (int t = 0; t < T; t++) {
			int min = Integer.MAX_VALUE;
			int N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			
			//33개 이상일 경우 반드시 같은 원소가 3개 존재
			if(N > 32) {
				System.out.println(0);
				continue;
			}
			
			String[] mbti = new String[N];
			for (int n = 0; n < N; n++) {
				mbti[n] = st.nextToken();
			}

			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					for (int k = j + 1; k < N; k++) {
						min = Math.min((PsychicDistance(mbti[i], mbti[j]) + PsychicDistance(mbti[i], mbti[k])
								+ PsychicDistance(mbti[j], mbti[k])), min);
						
						if(min == 0) {
							break;
						}
					}
				}
			}
			
			System.out.println(min);
		}
	}

	// 심리 거리 재는 함수
	public static int PsychicDistance(String a, String b) {
		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			if (a.charAt(i) != b.charAt(i)) {
				cnt++;
			}
		}
		return cnt;
	}

}

결과

회고

• 멍청하게 st를 continue 구문 뒤에 써버려서 포맷 에러 뜨는 것도 못찾다가 질문을 통해 알아냈다.
• 다시는 그러지말자