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

문제

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

프로그래머스

---

문제 풀이

해당 문제는 같은 토핑 가짓수로 나눌 수 있는 방법의 수를 반환하는 문제이다. 그렇기 때문에 모든 케이스를 확인해볼 필요가 있었다.

 

이때 모든 자르는 방법 마다 양쪽의 토핑 수를 카운트하면 시간 초과가 날 것 같았다.

 -> 시간 복잡도는 n^n이므로 최대 100000^100000이다.

 

그렇기에 초기 값을 구한 후 순서대로 올라가며 계산된 map에서 right -> left으로 값을 전달하면서 가짓수를 확인했다.

 

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    map<int ,int> mapA;
    map<int ,int> mapB;
    
    int countA = 0;
    int countB = 0;
    
    for(int x : topping){
        if(mapB.find(x) != mapB.end()){
            mapB[x]++;
        }else{
            mapB[x] = 1;
            countB++;
        }
    }
    for(int i = 0; i < topping.size(); i++){
        
        if(mapB[topping[i]] == 1){
            mapB.erase(topping[i]);
            countB--;
        }else{
            mapB[topping[i]]--;
        }
        
        if(mapA.find(topping[i]) != mapA.end()){
            mapA[topping[i]]++;
        }else{
            mapA[topping[i]] = 1;
            countA++;
        }
        
        if(countA == countB)answer++;
    }
    
    return answer;
}