백준_가장 가까운 세 사람의 심리적 거리_20529

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

문제

여러분은 요즘 유행하는 심리검사인 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 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

출력

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

예제 입력

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

예제 출력

8
0
4

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let T = +input[0]; // 테스트 케이스 개수
let line = 1;

// 조합
const combinationFun = (arr, selectedNum) => {
  if (selectedNum === 1) return arr.map((a) => [a]);
  const result = [];
  arr.map((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combi = combinationFun(rest, selectedNum - 1);
    const attached = combi.map((com) => [fixed, ...com]);
    result.push(...attached);
  });
  return result;
};

// 두 사람의 심리적 거리 구하기
const distance = (mbti1, mbti2) => {
  let len = 0;
  for (let i = 0; i < 4; i += 1) {
    if (mbti1[i] !== mbti2[i]) len += 1;
  }
  return len;
};

let answer = '';
while (T > 0) {
  const N = +input[line];
  const listOfMBTI = input[line + 1].split(' ');
  let result = Number.MAX_SAFE_INTEGER;
  if (N > 32) result = 0;
  else {
    const combination = combinationFun(listOfMBTI, 3);

    for (let comb of combination) {
      let dis = 0;
      dis += distance(comb[0], comb[1]);
      dis += distance(comb[1], comb[2]);
      dis += distance(comb[2], comb[0]);
      result = Math.min(result, dis);
    }
  }
  answer += result + '\n';
  line += 2;
  T -= 1;
}

answer = answer.trimEnd();
console.log(answer);

풀이 및 해설

• 심리적 거리가 최소인 세 사람의 심리적 거리 구하기

1. 각 사람들의 심리적 거리 구한 후 최소 3개 선택 ⇒ 시간초과 발생

2. 비둘기집 원리 이용

   1. MBTI가 총 16가지 이므로 N이 33이상일 경우 MBTI가 겹치는 사람이 3명 이상 존재하므로 ⇒ 심리적 거리는 0

   2. 조합 이용하여 세 사람의 심리적 거리 구해서 최소값 갱신

      

   ⇒ 여기서 조합을 백트래킹 이용해서 풀면 메모리와 시간 단축

   

   const fs = require('fs');
   const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
   
   let T = +input[0]; // 테스트 케이스 개수
   let line = 1;
   
   // 두 사람의 리적 거리 구하기
   const distanceFunc = (mbti1, mbti2) => {
     let sum = 0;
     for (let i = 0; i < 4; i += 1) {
       if (mbti1[i] !== mbti2[i]) sum += 1;
     }
     return sum;
   };
   
   let answer = '';
   while (T > 0) {
     const N = +input[line];
     const listOfMBTI = input[line + 1].split(' ');
     let result = Number.MAX_SAFE_INTEGER;
     // MBTI가 총 16가지 이므로 N이 33 이상이면 같은 MBTI를 가진 사람이 3명이상 존재
     // 따라서 MBTI가 같은 세 사람을 선택하면 최소 심리적 거리는 0
     if (N > 32) result = 0;
     else {
       const visited = new Array(N).fill(false);
       // 백트래킹 수행(조합)
       const backtracking = (idx, selected) => {
         if (selected.length === 3) {
           let sum = 0;
           sum +=
             distanceFunc(selected[0], selected[1]) +
             distanceFunc(selected[1], selected[2]) +
             distanceFunc(selected[2], selected[0]);
           result = Math.min(result, sum);
           return;
         }
         for (let i = idx + 1; i < N; i += 1) {
           if (!visited[i]) {
             visited[i] = true;
             backtracking(i, [...selected, listOfMBTI[i]]);
             visited[i] = false;
           }
         }
       };
       backtracking(-1, []);
     }
     answer += result + '\n';
     line += 2;
     T -= 1;
   }
   
   answer = answer.trimEnd();
   console.log(answer);

비둘기집 원리

n개의 상자에 n+1개의 물건을 넣는다고 가정할 때, 어느 한 상자에는 물건 두 개 이상이 들어있다는 원리

⇒ 모든 비둘기가 상자 안에 들어간다는 가정하에 귀류법을 통해 증명

n개의 상자와 n+1마리의 비둘기가 존재할 때, 각 상자에 비둘기가 한 마리 이하만 존재해야 한다면, 전체 상자에는 많아야 n마리의 비둘기가 존재한다. 하지만, 비둘기가 n+1마리이므로 모순 발생!