[TIL #17] 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

롤케이크 하면 떠오르는 모 캐릭터가 있지만 여기서 꺼낼 건 아니니 넘어가자...

 

롤케이크 위에 토핑이 있고, 두 사람이 이를 균등히 나눌 수 있는 경우의 수를 모두 찾는 문제.

그 길이는 최대 1백만이고, 개수는 최대 1만이다.

아니 뭘 이리 많이 먹어...

 

길이가 최대 1백만이라 2중 for문은 절대 사용해선 안된다.

단일 for문만을 사용하여 문제를 풀어야 하겠다.

양 쪽의 경우에 대해서 생각해야 하니 떠오르는 방법은...

"투포인터"가 되겠다.

각각 2개씩의 배열과 ``Set``을 사용해서 풀 수 있을 것 같다.

``Set``은 당연히 중복 필터링을 위해,

배열은 토핑 개수 카운팅을 위해 사용할 것이다.

 

왼쪽부터 카운팅 해 보자.

const n = topping.length;
const lTopCnt = new Array(n).fill(0);
const rTopCnt = new Array(n).fill(0);

const lSet = new Set();
const rSet = new Set();

let topCnt = 0;

// 왼쪽에서 오른쪽으로 순회하며 고유 토핑 개수 기록
for (let i = 0; i < n; i++) {
    const top = topping[i];
    if (!lSet.has(top)) {
        topCnt++;
        lSet.add(top);
    }
    lTopCnt[i] = topCnt;
}

왼쪽에서 오른쪽으로 배열을 순회한다.

인덱스에 해당하는 토핑이 ``Set``에 없으면 ``topCnt``를 늘려 카운팅 한다.

이미 ``Set``에 있다면 추가 카운팅을 할 필요가 없다.

 

오른쪽에서 시작하는 순회도 마찬가지.

topCnt = 0;

// 오른쪽에서 왼쪽으로 순회하며 고유 토핑 개수 기록
for (let i = n - 1; i >= 0; i--) {
    const top = topping[i];
    if (!rSet.has(top)) {
        topCnt++;
        rSet.add(top);
    }
    rTopCnt[i] = topCnt;

방향이 반대일 뿐 하는 일은 똑같다.

 

자 이러면 ``Set``의 역할은 여기서 끝이다.

배열엔 각 위치 별 토핑 카운트가 들어가 있다.

떨어진 지점을 자르는 게 아니라 제대로 2분할을 해야 한다는 점을 기억하자.

// 분할 가능한 지점 찾기
let result = 0;
for (let i = 0; i < n - 1; i++) {
    if (lTopCnt[i] === rTopCnt[i + 1]) {
        result++;
    }
}

return result;

남은 부분 없이 2분할을 해야 하기 때문에 ``i``와 ``i + 1``로 비교하게 된다.

토핑의 개수가 같다면 ``result``를 증가시킨다.

카운팅이 끝나면 결과를 리턴하면 끝.

 

양쪽에서 공략해야 한다는 아이디어를 떠올릴 수 있다면,

슥슥 풀 수 있는 문제가 아니었을까.