LV2.롤케이크 자르기

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

프로그래머스

---

문제 내용 : 두 사람한테 [토핑 종류의 갯수가 똑같이 분배되게 하는 방법의 수]를 찾는 문제

ex) A : 1 ,2 ,4  / B : 2, 3 ,4 => 토핑 종류는 다르지만 토핑의 종류의 갯수가 같으므로 맞는 경우

ex) A : 1,1,2,3, / B : 1,2,2,2,3 =>토핑 종류 갯수 같음

 

우선 토핑 갯수 및 종류에 상관 없기에 중복을 허용하지 않으면 레드-블랙트리 기반으로하는 map 자료 구조를 사용하였다.

map<int,int> // 토핑종류 , 토핑 갯수

 

---

첫번째 접근 방법 : A한테 n개 ,B한테 [전체 - n개] 나눠주기

지문 그대로 나눠주고 그 결과가 맞는지를 체크하기로 했다.
하지만 이렇게 되면 topping을 순회하는 반복문 1개 ,반복문 안에서 나눠주는 반복문이 2개로 loop가 토핑갯수 하나마다 loop수가 제곱이되는 상황이 발생이 되어 시간복잡도에 문제가 발생

---

두번째 접근 방법 : A한테 topping을 다 몰아준 후 , 반복문이 한번 loop할때마다 B한테 하나씩 주기

이렇게 되면 인자값으로 주는 토핑 배열 길이만큼만 순회하면 모든 방법을 알 수 있다.

---

코드 영역

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

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    //A라는 사람의 topping map
    map<int,int>  map_A;
    //A의 빵에 모든 토핑을 올려놓기
    for (int elements : topping)
    {
        map<int, int> ::iterator iter = map_A.find(elements);

        if (iter != map_A.end()) iter->second++;
        else  map_A.insert({ elements,1 });
    }
    
     //A라는 사람의 topping map
    map<int, int> map_B;
    
     //토핑의 갯수만큼 순회를 하며 A의 토핑을 B한테 하나씩 주며 체크하기
    for (int i = 0; i < topping.size(); i++)
    {
        int pivot = topping[i];
 
        //map_A의 원소 제거 (B한테 하나 주기)
        map<int, int> ::iterator iter = map_A.find(pivot);
        if (iter != map_A.end())
        {
            iter->second--;
            if (iter->second <= 0) map_A.erase(iter);
        }

        //map_B의 원소 추가 (A한테서 받은 토핑 추가하기)
        iter = map_B.find(pivot);
        if (iter != map_B.end()) iter->second++;
        else  map_B.insert({ pivot,1 });

        //각 토핑의 map갯수가 같은지 체크 
        if (map_A.size() == map_B.size()) answer++;
    }

    return answer;
}