[구현] 상어 초등학교

[ericagong]

⭐ 성찰

1. 시간 복잡도 감소시키기 위해, 특정 값의 존재 여부를 바로 확인해야하면 set/map 타입 사용하기 ⭐ 배열 지양 ⭐
2. 완전 탐색이 필요한 경우, 반드시 시간 복잡도를 먼저 생각해 (1) 가능한지 (2) 탐색 시간을 줄일 수 있는 방법은 무엇이 있을지 고민해야함

❓ 문제 상황

상어 초등학교

👨‍💻 문제 해결

✅ 1차 풀이: 구현

⏳ 시간 복잡도 계산

[시간복잡도]
n*2 * n*2 * nlogn = O(n*5logn), 
학생 수 * 최대 빈 자리 * 정렬
-> 3 ≤ N ≤ 20 이므로 4,163,295 <= 10,000,000
-> JS는 코테 환경에서 1초에 1000만 내의 연산 수행 가능
-> `완전탐색` 가능

1. 정해진 순서대로 학생별 최적 자리 구하기

• 학생 별 좋아하는 학생 4명을 map에 key = 학생 index, value = 좋아하는 학생 set으로 저장
• ** 배열이 아닌 set을 사용해 set.prototype.has로 특정 값에 바로 접근하게 함 **
• 모든 빈 자리에 대해 [numFav, numEmpty, x, y] 형태의 정보를 만들고, 정렬하여 최적 자리 구하기

2. 전체 자리에 대해 만족도 계산

const fs = require("fs");
const inputs = fs.readFileSync("/dev/stdin").toString().split("\n");

const N = Number(inputs.shift());
const g = Array.from({ length: N }, () => new Array(N).fill(0));

const favs = new Map();
const orders = [];
for (let i = 0; i < N * N; i++) {
  const [num, ...fav] = inputs.shift().split(" ").map(Number);
  orders.push(num);
  favs.set(num, new Set(fav));
}

// 디버깅용 로거
// function log() {
//   for(let i = 0; i < g.length; i++) {
//     console.log(g[i].join(' '))
//   }
//   console.log()
// }

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
// log()

// 모든 학생에 대해 적절한 자리 찾기
orders.forEach((num) => {
  const targets = [];
  for (let x = 0; x < N; x++) {
    for (let y = 0; y < N; y++) {
      if (g[x][y] !== 0) continue;

      let num_fav = 0;
      let num_empty = 0;
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        if (g[nx][ny] === 0) num_empty += 1;
        else if (favs.get(num).has(g[nx][ny])) num_fav += 1;
      }

      targets.push([num_fav, num_empty, x, y]);
    }
  }

  // 최적의 자리 선택 위해 문제 조건대로 정렬
  targets.sort((a, b) => {
    if (a[0] !== b[0]) return b[0] - a[0];
    if (a[1] !== b[1]) return b[1] - a[1];
    if (a[2] !== b[2]) return a[2] - b[2];
    return a[3] - b[3];
  });

  const [_, __, tx, ty] = targets[0];
  g[tx][ty] = num;
});

// log()

// 전체 만족도 계산
let satisfaction = 0;
for (let x = 0; x < N; x++) {
  for (let y = 0; y < N; y++) {
    const num = g[x][y];
    let num_fav = 0;

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
      if (favs.get(num).has(g[nx][ny])) num_fav += 1;
    }

    if (num_fav === 0) continue;
    else satisfaction += Math.pow(10, num_fav - 1);
  }
}

console.log(satisfaction);