프로그래머스 132265 - 롤케이크 자르기 (Lv.5)

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

// 프로그래머스 132265 - 롤케이크 자르기 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/132265

// 문제 설명
// 롤케이크에 놓인 토핑이 일렬로 주어진다(topping[i] = i번째 토핑의 번호).
// 케이크를 한 번 잘라 두 조각으로 나눌 때, 두 조각의 "토핑 종류 수"가 같으면 공평한 분배다.
// 공평하게 자르는 방법의 수를 반환하라.

// 제약 조건
// 1 <= topping 길이 <= 1,000,000
// 1 <= topping[i] <= 10,000

// Example
// Input : [1, 2, 1, 3, 1, 4, 1, 2]
// Output: 2   ([1,2,1,3] / [1,4,1,2] 와 [1,2,1,3,1] / [4,1,2] — 양쪽 다 3종류)
//
// Input : [1, 2, 3, 1, 4]
// Output: 0   (어디를 잘라도 종류 수가 어긋난다)

// 접근 — 접미 종류 수 배열 + 접두 스캔
// 자르는 위치는 n-1가지. 위치마다 양쪽 종류를 새로 세면 O(n^2) = 최악 10^12로 시간 초과.
// 양쪽 집계를 "한 번씩만" 훑도록 나눈다.
// 1) 오른쪽 끝에서 왼쪽으로 훑으며 rightKinds[i] = i..n-1 구간의 종류 수를 저장한다.
//    개수 배열 cntR을 두고, 어떤 토핑이 처음 등장할 때(개수가 0에서 1이 될 때)만 종류 수를 +1.
// 2) 다시 왼쪽에서 오른쪽으로 훑으며 0..i 구간의 종류 수를 같은 방식으로 굴린다.
//    이때 rightKinds[i+1]과 같으면 i / i+1 사이를 자른 것이 공평한 분배.
// 3) i는 n-2까지만 — 마지막 원소 뒤를 자르면 오른쪽 조각이 비어버린다.
// 시간 O(n), 공간 O(n + 10000)

#include <vector>

using namespace std;

int rightKinds[1000000];    // rightKinds[i] = i번째부터 끝까지의 토핑 종류 수
int cntR[10001];            // 오른쪽 조각의 토핑별 개수
int cntL[10001];            // 왼쪽 조각의 토핑별 개수

int solution(vector<int> topping) {
    int n = topping.size();

    int kinds = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (cntR[topping[i]]++ == 0) kinds++;       // 처음 등장한 토핑일 때만 종류 +1
        rightKinds[i] = kinds;
    }

    int answer = 0;
    kinds = 0;
    for (int i = 0; i < n - 1; i++) {               // 마지막 원소 뒤는 자를 수 없다
        if (cntL[topping[i]]++ == 0) kinds++;
        if (kinds == rightKinds[i + 1]) answer++;   // i까지 / i+1부터로 갈랐을 때 종류 수 일치
    }
    return answer;
}

정리

• “모든 분할점에서 양쪽을 집계”는 누적 배열 신호다. 분할점마다 독립적으로 세면 O(n²)이고 n = 10⁶라 10¹²로 즉사한다. 한쪽을 미리 배열에 접어두고 반대쪽을 스캔하면 총 두 번의 선형 순회로 끝난다 — 누적합 문제에서 prefix[i]를 미리 만드는 것과 정확히 같은 구조이고, 값이 “합”이 아니라 “종류 수”로 바뀌었을 뿐이다.
• 종류 수 갱신의 핵심은 if (cnt[v]++ == 0) kinds++ 한 줄. 후위 증가는 증가 전 값을 돌려주므로, 개수를 올리는 동작과 “처음 등장인가” 판정이 한 번의 배열 접근으로 합쳐진다. set에 넣고 size()를 읽으면 원소마다 O(log n)이 붙고 조각마다 새 컨테이너가 필요해진다.
• 토핑 번호가 1~10,000으로 작아서 unordered_map 대신 고정 배열을 썼다. 값 범위가 배열로 감당되면 해싱·재해시·캐시 미스가 통째로 사라진다. 반대로 범위가 크거나 문자열 키면 unordered_map 카운팅으로 같은 로직을 그대로 옮길 수 있다(위장 42578에서 쓴 그 패턴).
• 한쪽만 배열로 남긴다는 선택도 의도적이다. 접미 종류 수는 나중에 다시 봐야 하니 rightKinds[n]이 필요하지만, 접두 종류 수는 스캔하며 즉시 소비하므로 스칼라 kinds 하나면 충분하다. 양쪽 다 배열로 만들면 메모리가 두 배가 되고 n = 10⁶에서는 그게 그대로 비용이다.
• 경계 조건 두 개: 루프 상한이 n - 1이어야 오른쪽 조각이 비지 않고, topping 길이가 1이면 자를 곳이 없어 자연히 0이 나온다. 커리큘럼 99번.
• 검증: 예제 2개(2, 0)와 [1,1]→1 통과, 완전 탐색 구현과 랜덤 2,000케이스 대조 전건 일치, n = 1,000,000 입력 0.003초 (MSVC /O2 /std:c++17).

핵심 요약 — 분할점마다 양쪽을 세면 O(n²)이지만, 접미 종류 수를 배열에 미리 접어두고 접두를 한 번 스캔하면 O(n)이 된다. 종류 수 갱신은 if (cnt[v]++ == 0) kinds++ 한 줄로, 후위 증가가 “개수 올리기”와 “첫 등장 판정”을 동시에 처리한다.