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

https://www.acmicpc.net/problem/20529

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	1536 MB	4043	1550	1185	36.744%

문제

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

예제 입력 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+2+1=4이다.

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2020! B번

• 문제를 검수한 사람: ahgus89, cgiosy, cheetose, cs71107, evenharder, gravekper, jhnah917, junseo, kdh9949, koosaga, queued_q, rdd6584, ryute
• 데이터를 추가한 사람: kimyh0316
• 문제를 만든 사람: leejseo, queued_q

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 비둘기집 원리

---

알고리즘 – 비둘기 집의 원리 (Pigeonhole Principle)

통과된 코드

비둘기 집의 원리를 이용하여 N > 32 인 경우를 처리해주는 것이 문제의 포인트

#include <iostream>
#include <vector>
using namespace std;
int _T, _N, _Res = INT32_MAX;
string _Str;
int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	cin >> _T;
	for (int i = 0; i < _T; i++) {
		cin >> _N;
		vector<string> _StrV;
		for (int i = 0; i < _N; i++) {
			cin >> _Str;
			_StrV.push_back(_Str);
		}
		if (_N > 32) {
			std::cout << 0 << "\n";
			continue;
		}
		int _Sum;
		_Res = INT32_MAX;
		for (int i = 0; i < _N; i++) {
			for (int j = i + 1; j < _N; j++) {
				for (int k = j + 1; k < _N; k++) {
					_Sum = 0;
					for (int q = 0; q < 4; q++) {
						if (_StrV[i][q] != _StrV[j][q]) _Sum++;
						if (_StrV[j][q] != _StrV[k][q]) _Sum++;
						if (_StrV[k][q] != _StrV[i][q]) _Sum++;
					}
					_Res = min(_Res, _Sum);
				}
			}
		}
		std::cout << _Res << "\n";
	}

	return 0;
}

더 효율적인 코드 (비트 마스킹)

비트마스킹을 이용하여 메모리 및 속도를 개선합니다.

#include <iostream>
#include <vector>
using namespace std;
int _T, _N, _Res = INT32_MAX;
vector<int> _bitV;
string _Str;
int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	cin >> _T;
	for (int i = 0; i < _T; i++) {
		cin >> _N;
		_bitV.clear();
		for (int i = 0; i < _N; i++) {
			cin >> _Str;
			int _bit = 0;
			if (_Str[0] == 'I') _bit += 1 << 0;
			if (_Str[1] == 'N') _bit += 1 << 1;
			if (_Str[2] == 'F') _bit += 1 << 2;
			if (_Str[3] == 'P') _bit += 1 << 3;
			_bitV.push_back(_bit);
		}
		if (_N > 32) {
			std::cout << 0 << "\n";
			continue;
		}
		int _Sum;
		_Res = INT32_MAX;
		for (int i = 0; i < _N; i++) {
			for (int j = i + 1; j < _N; j++) {
				for (int k = j + 1; k < _N; k++) {
					_Sum = 0;
					for (int q = 0; q < 4; q++) {
						if ((_bitV[i] & (1 << q)) != (_bitV[j] & (1 << q))) _Sum++;
						if ((_bitV[j] & (1 << q)) != (_bitV[k] & (1 << q))) _Sum++;
						if ((_bitV[k] & (1 << q)) != (_bitV[i] & (1 << q))) _Sum++;
					}
					_Res = min(_Res, _Sum);
				}
			}
		}
		std::cout << _Res << "\n";
	}

	return 0;
}