[백준 15565 - Node.js] 귀여운 라이언

🔗 문제 링크

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

15565번: 귀여운 라이언

✏️ 풀이

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

let count = 0;
let minCount = Infinity;
let i = 0;
let j = 0;

while (j < N) {
  if (dolls[j] === 1) {
    count++;
  }

  while (count === K) {
    if (dolls[i] === 1) {
      count--;
    }
    minCount = Math.min(minCount, j - i + 1);
    i++;
  }

  j++;
}

console.log(minCount === Infinity ? -1 : minCount);

집합의 시작점을 i, 끝을 j라고 할 때, j를 1씩 증가시키면서 dolls[j]가 라이언 인형일 때마다 count를 증가시킨다.

 

만약 count가 K개가 되었다면 시작점 i를 가장 가까운 라이언 인형의 인덱스까지 증가시킨 후에 집합의 최소 크기를 갱신한다. count가 K개일 때 집합 크기가 최소가 되려면 집합의 맨 앞 뒤가 모두 라이언 인형일 수밖에 없으므로 이렇게 하였다.

 

반복이 끝났을 때 minCount가 갱신된 적이 없으면 -1을 반환하고, 그 외에는 갱신된 minCount를 반환한다.