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

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

프로그래머스

 

set + 단순반복 = 시간초과

map + 조각넘기기방식 적용으로 해결

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

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    int tSize = topping.size();
    map<int, int> c1, c2; // topping type, count
    
    // 안자른상태
    for(int i=0; i<tSize; i++){
        map<int,int>::iterator it = c1.find(topping[i]);
        if(it != c1.end())
            (it->second)++;            
        else
            c1.insert(make_pair(topping[i], 1));
    }
    
    // 자른 범위를 한칸씩 늘리면서 공평여부 check
    for(int i=tSize-1; i>0; i--){
        map<int,int>::iterator it = c1.find(topping[i]);
        if(it->second == 1){
            c1.erase(topping[i]);
        }
        else{
            (it->second)--;
        }
        
        it = c2.find(topping[i]);
        if(it != c2.end())
            (it->second)++;            
        else
            c2.insert(make_pair(topping[i], 1));
        
        if(c1.size() == c2.size())
            answer++;
    }
    
    return answer;
}