[백준 20922 - Node.js] 겹치는 건 싫어

🔗 문제 링크

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

20922번: 겹치는 건 싫어

✏️ 풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const [[N, K], arr] = input.map(v => v.split(' ').map(Number));

const intMap = {};
let maxLength = 0;
let i = 0;
let j = 0;

while (i <= j && j < N) {
  while (intMap[arr[j]] === K) {
    intMap[arr[i]]--;
    i++;
  }
  maxLength = Math.max(maxLength, j - i + 1);
  intMap[arr[j]] = (intMap[arr[j]] ?? 0) + 1;
  j++;
}

console.log(maxLength);

 

arr[i]를 수열의 첫 번째 원소, arr[j]를 수열의 마지막 원소라고 할 때, j를 증가시키면서 intMap에 각 수가 등장한 횟수를 갱신한다.

 

j를 증가시키기 전에 먼저 arr[j]에 해당하는 수가 이미 수열에 몇 번 등장하는지 확인하여 만약 그 수가 K개라면 arr[j]를 포함시키면 K + 1개가 되어 문제의 조건인 "같은 원소가 K개 이하"임을 만족하지 못하게 된다. 따라서 arr[j]를 수열에 포함시키기 전에 i를 계속 증가시키면서 arr[j]와 동일한 수가 수열에서 한 번 제거될 때까지 arr[i]를 수열에서 제거한다.

 

j가 N - 1일 때까지 반복하면서 조건을 만족하는 부분 수열의 길이를 매번 갱신하면 반복문이 끝날 때의 maxLength가 정답이 된다.