백준 20529번 (가장 가까운 세 사람의 심리적 거리, C++) [BAEKJOON]

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

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초1536 MB40431550118536.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번

알고리즘 분류


통과된 코드

비둘기 집의 원리를 이용하여 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;
}

백준 20529번 (가장 가까운 세 사람의 심리적 거리, C++) [BAEKJOON]”의 1개의 생각

  1. 핑백: 알고리즘 – 비둘기 집의 원리 (Pigeonhole Principle) - 어제와 내일의 나 그 사이의 이야기

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다