프로그래머스 - 롤케이크 자르기 [C++]

 이 문제는 맵을 이용해서 풀었다. topping의 최대 길이는 100만이므로, O(n) 시간 이하의 알고리즘을 써야만 시간 안에 풀 수 있다. 절반을 자르는 로직은 왼쪽은 topping의 처음부터 half를 포함하는 범위까지로, 오른쪽은 half + 1부터 마지막까지로 정했다. topping을 순회하면서 절반을 자르고, 여기서 추가 반복문을 사용하지 않기 위해 map으로 해당 숫자의 count를 저장하고, left에서는 해당 값이 0일때 추가되면 leftCnt++을, right에서는 해당 값이 0이 되면 rightCnt--을 수행하여 정답을 도출했다.

 

 

 

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    if (topping.size() == 1) {
        return 0;
    }
    
    map<int, int> left;
    map<int, int> right;
    
    int leftCnt = 0;
    int rightCnt = 0;
    
    for (int t : topping) {
        if (right[t] == 0) {
            rightCnt++;
        }
        right[t]++;
    }
    
    int half = 0;
    while (half < topping.size()) {
        
        int present = topping[half];
        
        // right에서 빼기
        right[present]--;
        
        if (right[present] == 0) {
            rightCnt--;
        }
        
        // left에 더하기
        if (left[present] == 0) {
            leftCnt++;
        }
        left[present]++;
        
        if (leftCnt == rightCnt) {
            answer++;
        }
        
        half++;
    }
    
    return answer;
}