[백준2531_자바스크립트(javascript)] - 회전 초밥

🔴 문제

회전 초밥

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const [n, d, k, c] = inputs.shift().split(' ').map(Number);
const sushi = inputs.map(Number);
sushi.push(...sushi);

const count = Array(d + 1).fill(0);
let ans = 0;
let kind = 0;

for (let i = 0; i < k; i++) {
  const idx = sushi[i];
  if (count[idx] === 0) kind++;
  count[idx]++;
}

for (let i = 0; i < n; i++) {
  ans = Math.max(ans, kind + (count[c] ? 0 : 1));

  const start = sushi[i];
  const end = sushi[i + k];

  count[start] -= 1;
  if (count[start] === 0) kind--;

  if (count[end] === 0) kind++;
  count[end] += 1;
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

슬라이딩 윈도우 유형의 문제다.

언뜻보면 "배열에서 앞 요소를 빼고, 뒤 요소를 추가하면서 벨트를 회전시키고 앞에서부터 K개의 초밥의 종류의 개수를 카운팅 하면 되지 않나?"라고 생각할 수 있다.
하지만 배열에서 앞 요소를 빼는shift) 작업은O(n)의 시간복잡도를 가진다. 게다가 이 행동을 n+k번 반복해야 하기 때문에 최종적으로는 O(n^2)의 시간복잡도를 가지게 된다.
n이 최대 30,000인 이 문제에서는 최악의 경우 900,000,000번의 연산이 필요하므로 시간초과가 발생할 수 있다.

따라서 슬라이딩 윈도우와 인덱싱을 활용해 풀이해야 한다.

이 문제는 벨트가 원형 구조로 회전하기 때문에 스시 배열 끝에 스시를 이어 붙여 회전할 수 있도록 했다.
그 후 각 초밥 종류별 개수를 저장할 count 배열을 두고, 이 초밥을 처음 먹는 경우에는 kind 변수 값을 증가시킨다.

이제 슬라이딩 윈도우을 수행해야 되는데, 각 반복을 시작할 때 쿠폰 초밥을 포함했을 때의 초밥 종류 개수로 ans를 갱신한다.
그 후 맨 앞의 초밥은 제거, 맨 뒤 초밥은 추가하는데 이 때 초밥의 종류가 처음으로 증가하거나 카운팅 배열에서 사라지면 kind변수도 수정해줘야 한다.

🔵 Ref