[백준/G4] 8983 사냥꾼

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

시간복잡도

정렬 NlogN, for문과 그안의 이분탐색으로 인해
총 O(NlogN)

풀이

처음에는 이중for문(N**2)으로 사대기준 동물을 체크하는 방식이었는데
역시 사대와 동물의 수가 높아짐에 따라 (각각 최대 100000) 시간초과에 걸려서 23점이 나옴

23점 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./8983.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [M, N, L] = input[0].split(" ").map(Number);
const sadeList = input[1].split(" ").map(Number);
const animalList = input
  .slice(2)
  .map((animal) => animal.split(" ").map(Number));

let answer = 0;

// 사대마다 동물의 거리를 측정하여 사정거리보다 짧으면 cnt + 1
// 단 중복될 경우를 대비해서 check해야함

const maxX= Math.max(...animalList.map(pair => pair[0]));
const maxY = Math.max(...animalList.map(pair => pair[1]));

const check = Array.from({ length: maxX + 1}, () => Array.from({length: maxY+1}).fill(false));

for (const sadeX of sadeList) {
	for (const [x, y] of animalList){

		if (check[x][y]) continue

		let length = Math.abs(sadeX - x) + y

		if (length <= L) {
			check[x][y] = true
			answer += 1
		}
	}
}

console.log(answer)

그렇다면 NlogN으로 검색할 수 있는 방식을 찾아야했고
비교군을 반씩 줄여갈 수 있는 '이분탐색'의 방법이 있었다.

1. 먼저, 이분탐색을 위해 정렬이 필요해 x좌표만 주어지는 사대를 정렬(얘도 NlogN))한다.
2. 그다음 동물을 기준으로 가장 먼저 조건을 만족하는 사대를 찾는 이분탐색을 수행한다

+) L - y는 0보다 작아질 수 없으므로 미리 continue로 제외시킨다.
근데 메모리는 1MB정도 줄었지만 시간 상으로는 오히려 조금이지만 늘어버렸다
-> 드라마틱한 차이는 없었다

최종코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./8983.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [M, N, L] = input[0].split(" ").map(Number);
const sadeList = input[1].split(" ").map(Number);
const animalList = input
  .slice(2)
  .map((animal) => animal.split(" ").map(Number));

let answer = 0;

// '동물'을 기준으로 '사대' 탐색(사대가 x좌표만 있으므로 용이)

// 이진 탐색을 위한 정렬
sadeList.sort((a, b) => a - b);

for (const [x, y] of animalList) {
  let left = 0;
  let right = sadeList.length - 1;

  if (L - y < 0) continue;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let sadeX = sadeList[mid];
    let dist = Math.abs(sadeX - x) + y;

    if (dist <= L) {
      answer += 1;
      break;
    } else {
      // 조건을 만족하지 않을 때 비교할 사대를 바꿈(idx 업데이트)
      // ex) 사대가 동물보다 오른쪽에 있을경우-> 그 왼쪽 절반 중 새로 탐색
      if (sadeX > x) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
  }
}

console.log(answer);

52380KB 404ms