백준 15961 회전 초밥

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

문제

먹을 수 있는 초밥의 가짓수의 최댓값을 구해야 하는 문제이다. 여기서 무조건 초밥은 연속으로 가져가야 하기 때문에 k개의 연속된 요소들이 옮겨가면서 먹을 수 있는 가짓수를 구하면 되는 슬라이딩 윈도우 문제이다.

하나의 연속된 수열을 가지면서 계속 옆으로 옮겨가면서 구하면 될 것 같았지만

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [N, d, k, c] = inputs[0].split(" ").map(Number);
const sushi = inputs.slice(1).map(Number);
 
let max = 0;
for (let i = 0; i < N; i++) {
  const ateSushi = {};
  let cnt = 0;
  for (let j = 0; j < k; j++) {
    const sushiNum = sushi[(i + j) % N];
    if (!ateSushi[sushiNum]) {
      ateSushi[sushiNum] = 1;
      cnt++;
    }
  }
  if (!ateSushi[c]) cnt++;
  max = Math.max(max, cnt);
}
console.log(max);
 

이런 식으로 무식하게 도는 방법은 당연히 먹히지 않는다. 여기서 머리를 한번 더 굴려야 할 필요성이 있다. 슬라이딩 윈도우가 시간초과가 뜬다면 이를 더 효율적으로 사용할 수 있는 방법을 찾아야 한다.

슬라이딩 윈도우를 최적화하는 방법은 이전 값을 최대한 기억하면서 옮겨가는것이다. 따라서 맨 처음 k크기의 윈도우를 미리 만들어 놓고, 오른쪽으로 옮겨가면서 기존의 값에서 빼지는 초밥과 더해지는 초밥에 대해서만 계산을 하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [N, d, k, c] = inputs[0].split(" ").map(Number);
const sushi = inputs.slice(1).map(Number);
 
let max = 0;
let current = new Array(d + 1).fill(0);
let count = 0;
 
for (let i = 0; i < k; i++) {
  if (current[sushi[i]] === 0) count++;
  current[sushi[i]]++;
}
 
max = count;
 
for (let i = 0; i < N; i++) {
  if (max <= count) {
    if (current[c] === 0) max = count + 1;
    else max = count;
  }
 
  current[sushi[i]]--;
  if (current[sushi[i]] === 0) count--;
 
  const next = sushi[(i + k) % N];
  if (current[next] === 0) count++;
  current[next]++;
}
 
console.log(max);
 

이런 식으로 기존의 값은 최대한 기억하면서 이전 값을 빼고, 새로 들어올 값을 더한다. 여기서 next가 sushi[(i + k) % N]인 이유는 배열을 초과하더라도 회전초밥이기 때문에 다시 처음 요소로 가서 계산을 해야 하기 때문이다. 그렇게 추가되는 것과 빠지는 것을 계산함과 동시에 최댓값을 갱신시켜야 한다. 이 때, 이전에 먹었던 초밥 중에 쿠폰에서 제공하는 초밥이 없었다면 1개를 더해줘야 한다.

메모리가 참…많이 쓰인다