문제 개요

문제: 좋은 친구

분류: 자료 구조, 슬라이딩 윈도우, 큐

난이도: 골드4

문제 풀이

큐를 이용하여 풀었다.

• queue[len] : 이름의 길이가 len인 학생의 등수가 들어있는 큐

위와 같다고 할 때, 이름이 최대 20글자라고 했으므로 21개의 빈 배열을 원소로 갖는 배열을 선언한다.

입력이 성적순으로 주어지기 때문에 입력이 들어오는대로 순차적으로 탐색한다.

1. queue[len]에서 현재 등수(=현재 인덱스)와 K 넘게 차이나는 사람을 제거한다.
2. 정답 변수에 queue[len]의 남은 원소 개수를 누적하여 더한다.
3. queue[len]에 현재 등수를 추가한다.

코드

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

const solution = () => {
  const [N, K] = input.shift().split(" ").map(Number);
  const queue = Array.from(Array(21), () => []);
  let answer = 0;

  input.forEach((name, rank) => {
    const len = name.length;
    // 큐[이름의길이]에서 현재 등수와 K 넘게 차이나는 사람을 제거한다.
    while (queue[len].length > 0 && rank - queue[len][0] > K)
      queue[len].shift();
    answer += queue[len].length;
    queue[len].push(rank);
  });

  console.log(answer);
};

solution(input);