[lv2] 롤케이크 자르기

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

 

중복인 토핑을 카운트하지 않기 위해 set을 쓴다.

 

각각 왼/오른쪽 끝 부터 출발하여 토핑 가지수를 l[], r[]에 기록한다.

 

자르는 모든 경우의 수에 대해 lcnt와 rcnt가 같다면 answer++ 한다.

import java.util.*;

class Solution {
    int[] topping;
    int T, answer;
    // 왼/오른 쪽 부터 잘랐을 때 포함되는 토핑 개수
    int[] l, r;

    int solve() {

        Set<Integer> set = new HashSet<>();

        for(int i=0; i<T; i++) {
            set.add(topping[i]);
            l[i] = set.size();
        }

        set.clear();
        for(int i=T-1; i>=0; i--) {
            set.add(topping[i]);
            r[i] = set.size();
        }


        for(int i=0; i<T-1; i++) {
            if(l[i] == r[i+1])
                answer++;
        }

        return answer;
    }

    public int solution(int[] topping) {
        this.topping = topping;
        T = topping.length;
        l = new int[T];
        r = new int[T];


        return solve();
    }
}