가장 가까운 세 사람의 심리적 거리(백준 코딩테스트 20529번, 완전탐색, NodeJS 풀이)

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

 

 

문제 수준:

실버1

 

문제 요약:

수많은 학생 중에 딱 3명을 뽑았을 때, mbti 알파벳의 차이가 가장 적은 조합이 어떻게 되는지를 판단하는 문제이다.

 

예를 들어,

INFP 학생과 INFP 학생은 완전 똑같으니 차이가 0이다.

INFP 학생과 INTP 학생은 알파벳 하나가 다르니 차이는 1이다.

 

이를 세 학생의 심리적 거리로 나타내면 

라고 할 수 있단다.

 

N명 (N >= 3)의 학생 중에서 가장 적은 차이를 보이는 엠비티아이 조합을 구하면 된다.

 

입출력 예 (입력 / 출력):

 

문제 풀이 아이디어:

그런데 조금 생각해보면 알 수 있는 사실이 있다.

(E / I), (N / S), (F / T), (P / J) 모두 알파벳은 두 개 뿐이므로,

특정 알파벳 위치 기준으로 보면, '모두 같거나' 혹은 '한 명만 다르고 두 명은 같거나'의 가능성 밖에 없다.

셋 다 다를 순 없다. 알파벳이 3개가 아니므로.

 

E, E, E => 0점,

E, I, I => 2점,

I, E, E => 2점,

...

I, I, I => 0점

 

이러니 MBTI 4자리 순회하면서 그 자리가 세 명 다 같으면 0점, 아니면 2점을 더해서 반환하는 함수를 만들 수 있다. 

function checkSame(a, b, c) {
  let score = 0;
  for (let i = 0; i < 4; i++) {
    if (a[i] === b[i] && a[i] === c[i] && b[i] === c[i]) {
      score += 0;
    } else {
      score += 2;
    }
  }
  return score;
}

 

 

그리고 N명 중 3명 뽑는건 이미 익숙한 완전 탐색 패턴으로 구현할 수 있다.

풀이 코드는 아래와 같다.

 

내 풀이:

1. closest라는 변수를 충분히 크게 선언해놓고 더 작은 조합이 나올때 마다 교체했다.

2. 재귀함수로 완전탐색을 구현했다. stack에 학생들을 담아 CEIL = 3에 닿으면 조합 차이를 계산하고 재귀에서 탈출한다.

 

위처럼 했다가 시간 초과가 나길래 새로 추가한 코드가 있는데,

재귀함수 로직 다음에 if (closest === 0) return 코드를 추가해줬다.

조합 차이가 0인게 발생했으면 다음 순회고 자시고 다 종료해버리면서 시간을 아낀다. (차이가 0보다 작을 순 없으므로 더 볼 필요가 없다.)

// 20529 가장 가까운 세 사람의 심리적 거리
let fs = require("fs");
let [n, ...arr] = fs.readFileSync("input.txt").toString().trim().split("\n");

for (let i = 0; i < arr.length; i++) {
  if (i % 2 === 0) continue;

  let closest = 100000;

  const list = arr[i].split(" ");
  const visited = new Array(list.length).fill(false);

  const stack = [];
  const CEIL = 3;

  function dfs(stack) {
    if (stack.length === CEIL) {
      let score = checkSame(...stack);

      if (score < closest) closest = score;
      return;
    }

    for (let i = 0; i < list.length; i++) {
      if (visited[i]) continue;
      stack.push(list[i]);
      visited[i] = true;
      dfs(stack);
      if (closest === 0) return
      stack.pop();
      visited[i] = false;
    }
  }

  dfs(stack);

  console.log(closest);
}

function checkSame(a, b, c) {
  let score = 0;
  for (let i = 0; i < 4; i++) {
    if (a[i] === b[i] && a[i] === c[i] && b[i] === c[i]) {
      score += 0;
    } else {
      score += 2;
    }
  }
  return score;
}