롤케이크 자르기

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

문제의 제한사항을 확인하고 브루트포스 기법으로는 해결할 수 없다는 생각이 들었다.
그래서 루프를 돌면서 현재 인덱스를 기준으로 왼쪽과 오른쪽을 나눠 set에 저장한 뒤, 두 개의 set 크기가 같다면 answer의 값을 증가 시켜주는 방향으로 문제를 해결하려했다.

✅ 초기 작성 코드

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> topping) 
{
    int answer = 0;
    for(int i = 0; i < topping.size(); ++i)
    {
        unordered_set<int> left(topping.begin(), topping.begin() + i + 1);
        unordered_set<int> right(topping.begin() + i + 1, topping.end());
        
        if(left.size() == right.size()) answer++;
    }
    
    return answer;
}

하지만 시간초과로 오답 처리가 되었다..
이유는 매 반복문 안에서 set을 범위 기반으로 초기화 하는 과정에서, 루프가 또 돌기 때문에 시간 복잡도 비용이 크게 증가하였던 것이다.
그래서 매 루프마다 set을 초기화 하는 것이 아니라, 미리 right에 모든 topping의 개수를 저장한 뒤, 전체 루프를 돌며 현재 인덱스 값을 left로 하나씩 옮겨가며 양쪽의 토핑 개수가 같은지 체크하는 방향으로 수정이 필요했다.

 

✅ 수정 코드

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

using namespace std;

int solution(vector<int> topping)
{
    int answer = 0;
    unordered_set<int> left;
    unordered_map<int, int> right;
    for (int t : topping)
    {
        right[t]++;
    }

    for (int t : topping)
    {
        right[t]--;
        left.insert(t);

        if (right[t] <= 0) right.erase(t);
        if (left.size() == right.size()) answer++;
    }

    return answer;
}

초기 모든 topping을 set에 넣는다면, 중복되어 존재하는 토핑을 확인할 수 없어 unordered_map으로 right를 선언하였고, left는 중복과 상관 없이, 토핑이 있는지 없는지만 판단하면 되기에 그대로 unodered_set으로 선언해주었다.

topping 전체를 순회하며 각 토핑이 몇 개 있는지 정리해서 right에 넣어주었고, 이후 다시 전체 루프를 돌며 right에선 현재 인덱스 토핑을 빼주고, left에 넣어주었다.
만약 right에 인덱스 토핑 개수가 0이라면, 해당 키 값을 삭제했고 left와 right의 개수가 같다면 answer의 값을 증가시켜주며 값을 도출했다.