롤케이크 자르기

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

프로그래머스

 

 

소스코드

import java.util.HashSet;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        HashSet<Integer> set = new HashSet<>();
        int arr1[] = new int[topping.length];
        int arr2[] = new int[topping.length];

        for (int i = 0; i < topping.length; i++) {
            set.add(topping[i]);
            arr1[i] = set.size();
        }
        set.clear();
        for (int i = topping.length - 1; i >= 0; i--) {
            set.add(topping[i]);
            arr2[i] = set.size();
        }

        for (int i = 0; i < topping.length - 1; i++) {
            if (arr1[i] == arr2[i + 1]) answer++;
        }

        return answer;
    }
}

 

 

해결방법

앞에서부터 토핑의 개수를 세서 arr1 배열에 저장한다.

뒤에서부터 토핑의 개수를 세서 arr2 배열에 저장한다.

arr1[i]과 arr2[i+1]이 같다면 두 조각의 토핑의 개수는 동일한 것으로 결과값을 증가시킨다.