[Silver I] 가장 가까운 세 사람의 심리적 거리 - 20529

문제 링크

성능 요약

메모리: 18408 KB, 시간: 192 ms

분류

브루트포스 알고리즘, 비둘기집 원리

제출 일자

2024년 5월 16일 14:54:53

문제 설명

여러분은 요즘 유행하는 심리검사인 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$$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, C$가 있을 때 이들의 심리적인 거리는

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

로 정의한다.

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

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

입력

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

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

출력

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

풀이

비둘기집 원리를 이용해야 시간초과없이 해결할 수 있는 문제이다.
[비둘기집 원리 - 나무위키]
간단히 요약하자면 전체 집단 n보다 큰 n+1은 반드시 하나는 겹친다는 원리이다.

MBTI는 16가지의 경우의 수가 있다. 비둘기집 원리에 따라 N이 32개를 넘어가게 되면 무조건 MBTI가 3명이 겹치게 되므로 거리는 0이 된다.

이 점을 참고하면 그래도 쉽게 접근할 수 있다.

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));
		int T = Integer.parseInt(br.readLine()); //데이터케이스 수 입력받기
		StringTokenizer st;
		
		for(int i=0; i<T; i++) {
			int N = Integer.parseInt(br.readLine());
			st= new StringTokenizer(br.readLine());
			
			if(N>32) { //32보다 크면 MBTI가 세명이 겹친다 -> 거리는 0
				System.out.println(0);
				continue;
			}
			//MBTI값 입력받기
			String[] MBTI = new String[N];
			for(int j = 0; j < N; j++) {
                MBTI[j] = st.nextToken();
            }
			
			int min_value = Integer.MAX_VALUE; //가장 짧은 거리 찾기
			for(int j = 0; j<N-2; j++) {
				for(int k = j+1; k<N-1; k++) {
					for(int l=k+1; l<N; l++) {
						//세 명의 거리 구하고 최솟값인지 확인
						min_value=Math.min(min_value, findDistance(MBTI[j],MBTI[k])
								+findDistance(MBTI[k],MBTI[l])+findDistance(MBTI[j],MBTI[l]));
					}
				}
			}
			System.out.println(min_value);
		}
		
	}
	//거리 구하기
	public static int findDistance(String str1,String str2) {
		int distance=0;
		for(int i=0; i<4; i++) {
			if(str1.charAt(i)!=str2.charAt(i)) {//MBTI 하나가 다를 때마다 +1
				distance++;
			}
		}
		return distance;
	}
}