[백준 2531 - Node.js] 회전 초밥

🔗 문제 링크

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

2531번: 회전 초밥

✏️ 풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const [N, d, k, c] = input[0].split(' ').map(Number);
const sushi = input.slice(1).map(Number);

let maxCount = 0;
let count = 0;
const seq = sushi.slice(0, k).reduce((acc, v) => {
  if (acc[v]) {
    acc[v]++;
  } else {
    acc[v] = 1;
    count++;
    maxCount++;
  }
  return acc;
}, {});

let i = 0;
let j = k - 1;

while (i < N) {
  if (seq[sushi[i]] === 1) {
    count--;
  }
  seq[sushi[i]]--;

  i++;
  j++;

  if (j === N) {
    j = 0;
  }

  if (seq[sushi[j]]) {
    seq[sushi[j]]++;
  } else {
    seq[sushi[j]] = 1;
    count++;
  }
  maxCount = Math.max(maxCount, count + !seq[c]);
}

console.log(maxCount);

최대한 많은 종류의 초밥을 먹으려면 k개의 연속된 초밥을 선택했을 때, 그 k개 안에 최대한 많은 종류의 초밥이 포함되어 있어야 한다. 그리고 만약 k개 중에 c번 초밥이 없다면 1개의 초밥(c번 초밥)을 더 먹을 수 있다.

 

먼저 0번째부터 (k - 1)번째까지 선택한 것으로 값들을 초기화한다. seq에는 현재 선택된 초밥들의 종류별 개수가 저장된다. 이후 시작점인 i와 끝점인 j를 증가시키면서 연속된 k개의 초밥을 1개씩 갱신해나간다. 즉, i번째 초밥을 버리고 (j + 1)번째 초밥을 추가하는 것이다. 여기서 (j + 1)이 N이 되면 회전 초밥이기 때문에 0으로 바꿔야 한다. i번째 초밥을 버릴 때 만약 i번째 초밥 종류가 단 1개라면 i번째 초밥을 버리면서 한 종류의 초밥을 선택하지 않게 되는 것이므로 count를 감소시킨다. 그리고 (j + 1)번째 초밥 종류가 단 1개라면 없던 종류의 초밥이 새롭게 선택된 것이므로 count를 증가시킨다.

 

count 증가 및 감소가 끝나면 현재 count와 지금까지의 count들의 최댓값인 maxCount를 비교하여 maxCount를 갱신한다. 이 때, 만약 c번 초밥이 현재 seq에 존재하지 않는다면 c번 초밥을 추가로 먹을 수 있기 때문에 (count + 1)과 비교한다.

 

회전 초밥이 한 바퀴 돌 때까지 위 과정을 반복한 후 maxCount를 출력하면 정답이다.