BOJ 1337 - 올바른 배열

문제

N개의 서로 다른 수가 주어질 때, 연속 5개의 수를 만들기 위해 추가해야 하는 최소 숫자 개수를 구하라.

입력

첫째 줄에 N, 이후 N줄에 각 수가 주어진다.

출력

추가해야 하는 최소 숫자 개수를 출력한다.

예제

입력	출력
`5` `1` `3` `5` `7` `9`	`3`

풀이

정렬 후 슬라이딩 윈도우로 길이 5 범위에 최대 몇 개가 포함되는지 확인한다.

배열을 정렬한다
각 원소를 시작점으로 arr[i]부터 arr[i]+4 범위에 포함되는 원소를 센다
범위 내 최대 원소 수를 구하고, 5에서 빼면 답이다

핵심 아이디어: 연속 5개 중 이미 존재하는 수가 많을수록 추가할 수가 적으며, 정렬 후 윈도우 탐색으로 O(N²)에 해결된다.

코드

const solution = (input) => {
  const N = +input[0];
  const arr = [];
  for (let i = 1; i <= N; i++) {
    arr.push(+input[i]);
  }
 
  arr.sort((a, b) => a - b);
 
  let maxCount = 0;
 
  for (let i = 0; i < N; i++) {
    let count = 0;
    for (let j = i; j < N; j++) {
      if (arr[j] - arr[i] < 5) count++;
      else break;
    }
    maxCount = Math.max(maxCount, count);
  }
 
  return 5 - maxCount;
};
 
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));

복잡도

시간: O(N log N)
공간: O(N)

문제