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

문제

 

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

프로그래머스

 

 

문제풀이

 

토핑의 개수는 상관없이 종류의 개수만 따지면 된다.

먼저 토핑 벡터를 탐색하면서 토핑 종류와 개수를 저장하는 map에 토핑 종류별 개수를 저장한다.

 

위 반복문이 종료됐으면 다시 반복문을 통해 토핑벡터를 탐색한다.

형 토핑을 저장하는 map에 토핑을 추가하고, 전체 토핑에서 현재 토핑의 개수를 한 개 없앤다.

만약 0개라면 erase를 통해 map에서 지운다.

 

형 map의 크기와 전체 토핑 map의 크기가 같다면 공평하게 나눈 것이므로 ++answer를 한다.

 

 

코드

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> topping) {
    int answer(0);
    unordered_map<int, int>types;
    unordered_map<int, int>older;

    for (int idx = 0; idx < topping.size(); ++idx)
        ++types[topping[idx]];

    for (int mid = 0; mid < topping.size(); ++mid) {
        ++older[topping[mid]];
        --types[topping[mid]];
        if (types[topping[mid]] == 0) types.erase(topping[mid]);
        if (older.size() == types.size()) ++answer;
    }

    return answer;
}