[백준/JS] 2531 회전초밥

문제

🧐 문제 풀이

슬라이딩 윈도우를 이용해서 풀면 됩니다.

슬라이딩 윈도우를 이동할 때 맨 뒷 값과 이전 슬라이딩 윈도우의 맨 앞 값을 계산해주면됩니다.

이와 같은 방식으로 연산해주면 됩니다.

그리고 end값이 맨 앞으로 넘어와야 하는 경우는

(현재index + 접시개수k) % 모든회전초밥수N 하면 됩니다.

잘못생각한 점

1. 슬라이딩 윈도우를 이상하게 사용함(?)

슬라이딩 윈도우는 사실상 맨 앞값과 맨 뒷 값만 비교해주면 됩니다.

하지만 저는 바보같이 for문을 이용해서 윈도우가 이동할때마다 먹을 수 있는 접시 갯수만큼 비교를 해주었습니다.
=> 이렇게 하면 당연히 시간초과가 나옵니더...ㅠㅠ

2. 최대 가짓 수 갱신 실수

카운트를 가장 큰 값으로 정해줄 때 잘못작성했습니다.

if (cnt >= ans) {
    if (check[c] == 0) cnt++;

    ans = cnt;
  }

위와 같이 갱신해주었는데 저렇게 되면 기존의 cnt 값에도 +1이 되어서 후에 진행되는 연산에 문제를 줍니다.

if (cnt >= ans) {
    if (check[c] == 0) {
      ans = cnt + 1;
    } else {
      ans = cnt;
    }
  }

3. 최대 가짓 수 갱신 조건문 위치

맨 처음 슬라이딩 윈도우가 최대 가짓수를 가질 수 있습니다. 따라서 초밥 쿠폰에 관련된 조건문은 반복문에 맨 앞에 위치해야 합니다.

따라서 위와 같이 ans 값에만 +을 하고 기존 cnt 값은 변경하지 않도록 해야 합니다.

4. 슬라이딩 윈도우 반복문을 0부터 시작할 것

1부터 시작하게 되면 0번째 경우를 간과하게 되므로 0부터 시작해야 합니다.

📝 결과 코드

참고블로그

const filePath = process.platform === "linux" ? "/dev/stdin" : "./test.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

let [N, d, k, c] = input.shift().split(" ").map(Number);

let check = Array(d + 1).fill(0);
let sushi = Array(N).fill(0);

for (let i = 0; i < N; i++) {
  sushi[i] = Number(input.shift());
}

let cnt = 0;
let ans = 0;

for (let i = 0; i < k; i++) {
  if (check[sushi[i]] == 0) {
    cnt++;
  }

  check[sushi[i]]++;
}

ans = cnt;

for (let s = 0; s < N; s++) {
  let end = (s + k) % N;

  //내가 원래 썼던 방식처럼 쓰면 cnt가 ++로 갱신되잖아 그니까 그럼 이제 여기서 연산할 때 문제가 되는거지
  if (cnt >= ans) {
    if (check[c] == 0) {
      ans = cnt + 1;
    } else {
      ans = cnt;
    }
  }

  check[sushi[s]]--;
  if (check[sushi[s]] == 0) cnt--;
  if (check[sushi[end]] == 0) cnt++;

  check[sushi[end]]++;
}

console.log(ans);