[프로그래머스] Lv.2 : 롤케이크 자르기 - 자바[Java]

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

프로그래머스

 

풀이

롤케이크를 잘랐을 때, 왼쪽과 오른쪽 롤케이크에 포함된 토핑 가짓수가 같은 경우의 수를 구해야 한다.

1<= 토핑의 길이 <= 10^6이므로 시간복잡도는 O(n)이어야 하므로, 누적합 배열과 비슷한 방식으로 로직을 짰다.

또한 Set을 사용하여 중복되는 원소를 제거하게 함으로써 토핑 가짓수를 구했다.

 

left[i] = 0~i번째 토핑까지의 토핑 가짓수

right[i] = n-1 ~ i번째 토핑까지의 토핑 가짓수

 

코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int n = topping.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        HashSet<Integer> leftSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            leftSet.add(topping[i]);
            left[i] = leftSet.size();
        }
        HashSet<Integer> rightSet = new HashSet<>();
        for (int i = n-1; i >= 0; i--) {
            rightSet.add(topping[i]);
            right[i] = rightSet.size();
        }
        
        int cnt = 0;
        for (int i = 0; i < n-1; i++) {
            if (left[i] == right[i+1]) {
                cnt++;
            }
        }
        return cnt;
    }
}