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

문제

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

프로그래머스

풀이

토핑 최대 개수가 백만개이기 때문에, 시간복잡도에 유의해야 한다.

루프를 여러번 돌면 시간초과가 나므로, 처음 top2 확인에 1번, 토핑 전체 검사 후 answer 증가에 1번 루프를 돈다.

먼저 토핑 전체를 검사해서, 서로 다른 토핑의 개수를 top2에 저장한다.

그 후에 토핑을 하나하나 확인해서, top1에 없는 토핑이라면 top1을 늘려준다.

top2에 토핑이 없어지면 top2를 1감소시킨다.

top1와 top2가 같다면 answer를 1증가시킨다.

소스 코드

#include <string>
#include <vector>
using namespace std;
 
bool top1Check[10001];
int top2Cnt[10001];
int top1 = 0;
int top2 = 0;
 
int solution(vector<int> topping) {
 
    for (int i = 0; i < topping.size(); i++)
    {
        if(top2Cnt[topping[i]] == 0)
        {
            top2++;
        }
        
        top2Cnt[topping[i]]++;
    }
    
    int answer = 0;
    
    for (int i = 0; i < topping.size(); i++)
    {
        int curTop = topping[i];
        
        if (top1Check[curTop] == false)
        {
            top1Check[curTop] = true;
            top1++;
        }
        
        top2Cnt[curTop]--;
        
        if(top2Cnt[curTop] == 0)
        {
            top2--;
        }
        
        if (top1 == top2)
        {
            answer++;
        }
    }
    
    return answer;
}