[백준 2230 - Node.js] 수 고르기

🔗 문제 링크

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

2230번: 수 고르기

✏️ 풀이

const [NM, ...input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const [N, M] = NM.split(' ').map(Number);
const arr = input.map(Number);

arr.sort((a, b) => a - b);
let minDiff = Infinity;
let start = 0;
let end = 0;

while (start <= end && end < N) {
  const curDiff = Math.abs(arr[start] - arr[end]);
  if (curDiff < M) {
    end++;
  } else {
    minDiff = Math.min(minDiff, curDiff);
    start++;
  }
  if (curDiff === M) {
    break;
  }
}

console.log(minDiff);

먼저 주어진 수열을 오름차순 정렬한다.

그 다음 시작 인덱스(start)와 끝 인덱스(end)를 모두 0으로 초기화하고 투 포인터로 최소 차이를 찾아낸다.

 

arr[start] 와 arr[end]의 차이를 구하고, 그 차이가 M보다 작다면 end를 증가시켜서 차이를 더 늘어나게 만든다. 차이가 M 이상이면 minDiff와 비교하여 갱신하고 start를 증가시켜서 다시 차이를 줄어들게 만든다. 그리고 만약 차이가 정확히 M과 같다면 이보다 더 작은 차이는 없으므로 즉시 반복문을 종료한다.

 

이렇게 투 포인터를 활용하면 O(n) 시간에 문제를 해결할 수 있다.