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

문제

---

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

풀이

---

같은 토핑(원소 값)의 개수에 상관없이 동일한 가짓수로 롤케이크을 자르는 경우의 수를 찾는 문제로, map을 활용해 토핑의 종류의 개수가 같은 경우의 수를 탐색한다. 롤케이크는 한 번만 자르므로 map 2개를 활용, 먼저 하나의 맵에 모든 토핑을 넣고 순서대로 다른 맵으로 이동하는 것을 반복하며 같은 map 사이즈를 가지고 있는 경우의 수를 종합하여 return한다.

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

using namespace std;

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

    map<int, int> front_topping;
    map<int, int> behind_topping;

    for (int i = 0; i < topping.size(); i++)
    {
        if (front_topping.find(topping[i]) != front_topping.end())
        {
            front_topping[topping[i]]++;
        }

        else
        {
            front_topping.insert({ topping[i],1 });
        }

    }

    for (int i = 0; i < topping.size(); i++)
    {
        if (behind_topping.find(topping[i]) != behind_topping.end())
        {
            behind_topping[topping[i]]++;
            front_topping[topping[i]]--;
        }

        else
        {
            behind_topping.insert({ topping[i],1 });
        }

        if (front_topping[topping[i]] == 1)
        {
            front_topping.erase(topping[i]);
        }

        if (front_topping.size() == behind_topping.size())
        {
            answer++;
        }
    }

    return answer;
}