[PRO] 프로그래머스 Lv.2 롤케이크 자르기 (Javascript)

문제

프로그래머스

 

문제 해석

접근 방법

칼로 롤케이크를 두 조각으로 나눌 때, 각 조각에 있는 토핑 종류의 개수가 같은 모든 경우의 수를 계산하는 문제입니다.

각 케이스에서 토핑 종류의 개수를 확인할 때 Set, Map 객체를 사용해 효율성을 높일 수 있습니다.

 

풀이 과정

칼을 가장 왼쪽에서부터 한 칸씩 오른쪽으로 이동하며 토핑의 종류를 계산합니다.

이 때 중복 계산을 줄이기 위해 칼을 이동할 때 오른쪽에서 왼쪽으로 넘어간 토핑의 정보만 업데이트하면 됩니다.

토핑 종류와 개수 탐색을 위해 왼쪽 롤케이크는 Set, 오른쪽 롤케이크는 Map으로 생성합니다.

 

왼쪽 롤케이크에는 토핑의 종류, 오른쪽 롤케이크는 토핑의 종류와 개수를 저장합니다.

초기값은 칼을 가장 왼쪽에 둔 상태이므로 모든 토핑의 종류와 개수를 오른쪽에 저장합니다.

 

그 다음 칼을 한 칸씩 이동하며 오른쪽에서 왼쪽으로 이동한 토핑에 대한 정보를 업데이트 합니다.

왼쪽 Set에 토핑의 종류를 추가하고 오른쪽 Map에 저장된 토핑의 개수에서 -1을 합니다.

오른쪽 Map의 경우 토핑의 개수가 0이 된다면 해당 토핑을 Map에서 삭제합니다.

업데이트 후 왼쪽 Set과 오른쪽 Map의 size가 동일하다면 경우의 수를 카운트합니다.

 

 

전체 코드

function solution(topping) {
    const left = new Set(),
        right = new Map();
    let ans = 0;
    for (let i = 0; i < topping.length; i++) {
        right.set(topping[i], (right.get(topping[i]) || 0) + 1);
    }

    for (let i = 0; i < topping.length; i++) {
        left.add(topping[i]);
        if (right.get(topping[i]) === 1) right.delete(topping[i]);
        else right.set(topping[i], right.get(topping[i]) - 1);
        if (left.size === right.size) ans++;
    }

    return ans;
}

 

회고

• 배열 정보를 탐색할 때 시간 효율을 위해 Array 대신 Map, Set 객체를 사용할 수 있다.