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

문제 링크

롤케이크 자르기

 

풀이

set으로 풀었는데 시간 초과가 나서 힌트를 얻은 문제
굳이 기준을 잡아서 할 필요 없이 둘로 나누는 것이기 때문에 기준에서 하나씩 빼면 된다.

1. set1에 toppings를 다 넣는다. 이 때 토핑의 개수를 생각해야하기 때문에 cnt 벡터로 토핑의 개수를 세준다.
2. 이제 토핑을 하나씩 빼서 set2에 넣어줄텐데, 하나 뺀 토핑의 개수가 0일 경우 set1에서 지워준다.
3. set1과 set2의 사이즈를 비교해서 같다면 answer++ 해준다.

 

코드

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

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;

    set<int> set1, set2;
    vector<int> cnt(topping.size(),0); // 토핑의 개수 배열
    for(int i=0;i<topping.size();i++)
    {
        set1.insert(topping[i]);
        cnt[topping[i]]++;
    }

    for(int i=0;i<topping.size();i++)
    {
        if(--cnt[topping[i]] == 0)
        {
            set1.erase(topping[i]);
        }
        set2.insert(topping[i]);
        if(set1.size() == set2.size()) answer++;
    }
    return answer;
}