[구현] 상어 초등학교

[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);