[Algorithm] Programmers :: 롤케이크 자르기

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

프로그래머스

int solution(vector<int> topping)
{
    if (topping.size() == 1) return 0;
    int answer = 0;
    map<int, bool> leftM;
    vector<int> leftV;
 
    map<int, bool> rightM;
    vector<int> rightV;
 
    int count = 0;
    for (int i = 0; i < topping.size(); ++i)
    {
        if (leftM[topping[i]]) leftV.push_back(count);
        else
        {
            ++count;
            leftM[topping[i]] = true;
            leftV.push_back(count);
        }
    }
 
    count = 0;
    for (int i = topping.size() - 1; i >= 0; --i)
    {
        if (rightM[topping[i]]) rightV.push_back(count);
        else
        {
            ++count;
            rightM[topping[i]] = true;
            rightV.push_back(count);
        }
    }
 
    reverse(rightV.begin(), rightV.end());
 
    for (int i = 0; i < leftV.size()-1; ++i)
    {
        if (leftV[i] == rightV[i + 1]) ++answer;
    }
 
    return answer;
}