문제 - 롤케이크 자르기

문제 설명

문제 접근

두개의 set을 쓰면서 왼쪽 오른쪽을 나눠서 모든 토핑의 개수를 세면서 하니 당연하게도 시간초과가 나왔다. 원소의 갯수는 1,000,000 이여서 O(N^2)이면 시간초과가 나오는 것이 당연하다. 그래서 미리 구간별로 토핑의 개수를 저장한 다음에 비교하여 결과를 출력했다.

ex) [1,2,1,3,1,4,1,2] 인 경우
왼쪽 구간별 토핑의 개수 0 ~ 7번 인덱스까지 : 1 2 2 3 3 4 4 4
오른쪽 구간별 토핑의 개수 7 ~ 0번 인덱스까지 : 4 4 4 3 3 2 2 1
즉 A[i] == B[i+1]인 경우에만 count++

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        int aryA[] = new int[topping.length];
        //왼쪽 구간별 토핑 갯수 저장
        Set<Integer> seta = new HashSet<>();
        for(int i=0;i<topping.length;i++)
        {
            if(!seta.contains(topping[i]))
            {
                seta.add(topping[i]);
            }
            aryA[i] = seta.size();
        }
        //오른쪽 구간별 토핑 갯수 저장
        int aryB[] = new int[topping.length];
        Set<Integer> setb = new HashSet<>();
        for(int i=topping.length-1;i>=0;i--)
        {
            if(!setb.contains(topping[i]))
            {
                setb.add(topping[i]);
            }
            aryB[i] = setb.size();
        }
        
        for(int i=0;i<topping.length-1;i++)
        {
            if(aryA[i] == aryB[i+1])
                answer++;
        }
        
        return answer;
    }
}