[JavaScript] 백준 15961 회전 초밥(JS)

SanE·2025년 4월 17일

JavaScript Map Sliding Window algorithm array two pointer

Algorithm

목록 보기

125/127

회전 초밥

📚 문제 설명

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 주어진다.
초밥 벨트에 있는 k개의 연속된 초밥을 먹는다고 할 때 먹을 수 있는 최대 종류는 총 몇 종류인가?

쿠폰 번호 c 종류의 초밥은 벨트에 없어도 주문하여 먹을 수 있다.

초밥 종류는 1부터 d 사이의 숫자가 주어진다.

👨🏻‍💻 풀이 과정

우선 문제를 읽고 가장 먼저 생각난 풀이는 Map을 사용하는 방법이었다.

슬라이딩 윈도우 알고리즘 설명은 이전 포스트를 참고.

슬라이딩 윈도우 알고리즘 이용.
초기 값을 반복문으로 Map에 저장.
쿠폰도 Map에 저장.
반복문으로 끝까지 순회하며 슬라이딩 윈도우를 이용하여 값을 비교.

💡Map 사용

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

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

const visitedMap = new Map();

// 초기값 설정.
for (let i = 0; i < k; i++) {
    const targetDish = input[i];
    if (!visitedMap.has(targetDish)) {
        visitedMap.set(targetDish, 1);
    } else {
        visitedMap.set(targetDish, visitedMap.get(targetDish) + 1);
    }

}

// 쿠폰 값 추가.
if (!visitedMap.has(c)) {
    visitedMap.set(c, 1);
} else {
    visitedMap.set(c, visitedMap.get(c) + 1);
}

// 최대 종류 갯수.
let max = visitedMap.size;

// 슬라이딩 윈도우 (처음부터 끝까지 확인)
for (let i = 0; i < N; i++) {
    const l = input[i];
    const nr = input[(i + k) % N];

  	// 왼쪽 값 제거.
    if (visitedMap.get(l) === 1) {
        visitedMap.delete(l);
    } else {
        visitedMap.set(l, visitedMap.get(l) - 1);
    }

	// 오른쪽 값 추가.
    if (!visitedMap.has(nr)) {
        visitedMap.set(nr, 1);
    } else {
        visitedMap.set(nr, visitedMap.get(nr) + 1);
    }

  	// 최대 갯수 갱신.
    max = Math.max(max, visitedMap.size);
}

console.log(max);

그런데 Map을 사용한 풀이보다 빠른 풀이가 있었다.
따라서 해당 풀이의

💡Map 사용 X

Map을 사용하지 않을 수 있는 이유는 초밥의 종류는 1부터 d 사이의 숫자이고 d는 3,000 이하의 정수이기 때문이다.
따라서 d 크기의 배열을 만들고 해당 배열을 Map 대신 사용하여 갯수를 카운팅하고
현재 종류의 갯수를 저장하는 변수를 이용하면 간단하게 바꿀 수 있다.

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

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

const visited = Array(d + 1).fill(0);
let setLength = 0;

// 초기값 설정.
for (let i = 0; i < k; i++) {
    const targetDish = input[i];
    if (visited[targetDish] === 0) {
        setLength++;
    }
    visited[targetDish]++;
}

// 쿠폰 값 추가.
if (visited[c] === 0) {
    setLength++;
}
visited[c]++;

// 최대 종류 갯수.
let max = setLength;

// 슬라이딩 윈도우 (처음부터 끝까지 확인)
for (let i = 0; i < N; i++) {
    const l = input[i];
    const nr = input[(i + k) % N];

    // 왼쪽 값 제거.
    visited[l]--;
    if (visited[l] === 0) {
        setLength--;
    }
  
	// 오른쪽 값 추가.
    visited[nr]++;
    if (visited[nr] === 1) {
        setLength++;
    }

    // 최대 갯수 갱신.
    max = Math.max(max, setLength);
}

console.log(max);

위에 있는 결과가 배열을 이용한 풀이의 결과,
아래 있는 결과가 Map을 이용한 풀이의 결과이다.

Why?
두 풀이 모두 시간 복잡도는 동일하다.
그러면 왜 Map을 이용한 풀이가 더 시간이 오래 걸리는 걸까?

실행 환경에 따라 다를 수 있지만, 가장 큰 이유는 Map 메서드를 이용하면서 발생하는 오버헤드 때문일 것 같다.
Map을 이용할 경우 set(), has() 등의 메서드를 사용하며 해당 메서드들이 콜스택에 쌓이게 되는데
이것은 단순히 배열 인덱스를 이용해 접근하는 방식보다 복잡하다.