[JS] 2230번 수 고르기

문제

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

 

풀이

전형적인 투 포인터 알고리즘을 이용해 두 수를 이용하는 문제다.

 

이 문제는 약간의 수학적인? 사고가 필요하다.

입력으로 받는 수열의 경우 정렬되지 않은 상태이다. 이런 수열 그대로를 투 포인터를 이용해 문제풀이 한다면 모든 경우의 수를 탐색해야 하기에 시간복잡도가 커질 수 있다.

 

이런 문제는 수열을 오름차순으로 정렬해주면 해결할 수 있다.

 

위의 경우에서 m보다 두 수의 차가 커졌다고 생각하자. 그렇다면 현제 lp에서 rp가 오른쪽의 수는 탐색할 이유가 있는가? 절대로 없다. 이유는 차가 가장 작은 수를 찾아야 하기 때문에 rp가 증가해 현제 lp와의 차가 커지는 수는 탐색할 필요가 없기 때문이다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e);

const [n, m] = input.shift().split(' ').map(Number);
const arr = input.map(Number);
let [lp, rp] = [0, 0];
let answer = Infinity;

arr.sort((a, b) => a - b);

while (lp < n && rp < n) {
  const sub = arr[rp] - arr[lp];

  if (sub < m) {
    rp++;
  }
  else if (sub >= m) {
    answer = Math.min(answer, sub);
    lp++;
  }
}

console.log(answer);