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

문제 해결을 위해선 결국 앞에서 부터 topping배열의 끝까지 모든 경우를 다 확인해 봐야 한다고 생각했습니다. 그런데 한번 배열을 자를때마다, 왼쪽 오른쪽 둘다 순회하면서 중복을 제외한 토핑의 가지수를 다 세는 경우에는 시간초과가 날 수 있는 Input 범위입니다( 최대 1,000,000 ). 결국 일일이 다 순회하지 말고 해결하라는 의도가 담겨 있는 문제이지요.

 

그래서 모든 순회를 하지 않는 선에서 갯수를 셀 수 있는 방법은 사실 map을 사용하는 경우 말고는 떠오르는 것이 없기 때문에 map을 잘 이용할 생각만 떠올린다면 LV2 치고는 쉬운 문제였다고 생각합니다. 아이디어를 떠올리고 나서 코드를 짜는건 5분도 안걸렸습니다. 생각보다 map을 이용해서 해결하는 문제가 많기 때문에 map의 활용은 정말 중요한 것 같습니다 !

 

 

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
//완탐은 시간초과
 
 
 
int solution(vector<int> topping) {
    int answer = 0;
    
    map<int,int> lm;
    map<int,int> rm;
    lm[topping[0]]++;
    for (int i=1;i<topping.size();i++)
    {
        rm[topping[i]]++;
    }
    
    int idx=0;
    while(idx<topping.size())
    {
        if (lm.size() == rm.size())
            answer++;
        idx++;
        lm[topping[idx]]++;
        rm[topping[idx]]--;
        if (rm[topping[idx]] == 0)
        {
            rm.erase(topping[idx]);
        }
    }
    
    
    return answer;
}