방과후
ALGORITHM NOTE약 2분

BOJ 20529 - 가장 가까운 세 사람의 심리적 거리

혹시 MBTI가 어떻게 되세요??

#algorithm#boj#silver#brute-force
아카이브로 돌아가기

문제 링크

문제

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

(AA와 BB 사이의 심리적인 거리) + (BB와 CC 사이의 심리적인 거리) + (AA와 CC 사이의 심리적인 거리)

로 정의한다.

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

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

입력

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

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

출력

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

풀이

세 사람을 고르는 문제라서 기본적으로는 모든 삼중 조합을 확인하면 된다. 코드에서도 세 개의 반복문으로 서로 다른 세 학생을 뽑고, checkMBTI로 세 쌍의 거리를 더해 최솟값을 갱신한다.

여기서 중요한 가지치기는 MBTI 종류가 16개뿐이라는 점이다. 학생 수가 충분히 많으면 같은 MBTI가 세 번 이상 반드시 나오므로 답은 바로 0이 된다. 코드의 N>33N > 33 처리도 그 점을 이용한 것이다.

즉 작은 입력에서는 브루트포스로 전부 확인하고, 큰 입력에서는 비둘기집 원리로 바로 결론을 내리는 구조다. 단순 완전탐색처럼 보여도 입력 제한을 잘 이용한 풀이가 핵심이다.

코드

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int checkMBTI(string s1, string s2) {
	int dis = 0;
 
	for (int i = 0; i < 4; i++) 
		if (s1[i] != s2[i]) dis++;
 
	return dis;
}
 
void solve() {
	int t, n;
	cin >> t;
 
	while (t--) {
		cin >> n;
		vector<string> v;
 
		for (int i = 0; i < n; i++) {
			string s;
			cin >> s;
			v.push_back(s);
		}
 
		int ans = 100;
 
		if (n > 33) 
			ans = 0;
		else {
			for (int i = 0; i < n - 2; i++) {
				for (int j = i + 1; j < n - 1; j++) {
					for (int k = j + 1; k < n; k++) {
 
						int tmp = checkMBTI(v[i], v[j]) + checkMBTI(v[j], v[k]) + checkMBTI(v[k], v[i]);
						ans = min(ans, tmp);
					}
				}
			}
		}
 
		cout << ans << '\n';
		
	}
		
}
 
int main() {
    
    ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도

  • 시간 복잡도: NN이 큰 경우 바로 종료하고, 아니면 세 명 조합을 확인하므로 O(min⁡(N,32)3)O(\min(N, 32)^3)이다.
  • 공간 복잡도: MBTI 목록을 저장하므로 O(N)O(N)이다.

마무리

작은 입력은 삼중 탐색, 큰 입력은 비둘기집 원리로 바로 0을 보는 분기 처리가 핵심이다.