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

https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=cpp

프로그래머스

 

처음에 모두 오른쪽에 담아두고 하나씩 꺼내서 왼쪽으로 이동시키면 되는 문제. 그러나 이 과정에서 반복문을 사용해 모두 열람하면 안되고 Set과 Map을 적절하게 사용하여 반복하지 않는 것이 중요하다. 

 

Map에 개수가 0이 되면 Set에서도 삭제하는 방식을 사용하면 현재 종류가 몇개 있는지 쉽게 파악하면서 진행할 수 있다. 

 

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

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    set<int> leftSet, rightSet;
    map<int, int> leftMap, rightMap;
    
    for(int i = 0; i < topping.size(); i++){
        rightSet.insert(topping[i]);
        rightMap[topping[i]]++;
    }
    
    for(int i = 0; i < topping.size(); i++){
        leftSet.insert(topping[i]);
        rightMap[topping[i]]--;
        
        if(rightMap[topping[i]] == 0){
            rightSet.erase(topping[i]);
        }
        
        if(leftSet.size() == rightSet.size()) answer++;
    }
    
    return answer;
}