[프로그래머스] 롤케이크 자르기, java

- 문제

프로그래머스

- 풀이

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        //왼쪽, 오른쪽에 있는 각각 같은 토핑의 개수를 세어놓기 위한 left right 배열을 선언합니다.
        //존재할 수 있는 topping 원소의 최대값이 10000이라 10001으로 선언하였습니다.
        int[] left = new int[10001];
        int[] right = new int[10001];
        
        //시작 시에는 left에 [0]번 인덱스 하나만 놓기 위해 topping[0]만 추가해줍니다.
        left[topping[0]]++;
        
        //right에는 [0]번을 제외한 1~마지막까지의 토핑 개수를 세어줍니다.
        for(int i=1; i<topping.length; i++){
            right[topping[i]]++;
        }
        
        //미리 만들어 놓은 count 함수를 통해 left, right의 토핑 개수를 세어줍니다.
        int leftCnt = count(left);
        int rightCnt = count(right);
        
        //최초로 케이크를 잘랐을 때 토핑의 수가 같다면 answer를 증가시켜 줍니다.
        if(leftCnt==rightCnt) answer++;
        
        //케이크 자르는 위치를 증가시켜가며 판단합니다.
        for(int i=1; i<topping.length-1; i++){
            
            //만약 왼쪽 롤케이크에 없던 토핑이 추가된다면 leftCnt를 증가시켜 줍니다.
            if(left[topping[i]]==0){
                leftCnt++;
            }
            //left 배열에 topping[i] 토핑의 수를 증가시킵니다.
            left[topping[i]]++;
            
            //만약 오른쪽 롤케이크에 존재하던 토핑이라면
            if(right[topping[i]]>0){
                
                //오른쪽 롤케이크에 해당 토핑의 개수가 하나였다면 rightCnt를 감소시킵니다.
                if(right[topping[i]]==1){
                    rightCnt--;
                }
                //right 배열의 topping[i] 토핑의 수를 감소시킵니다.
                right[topping[i]]--;
            }
            
            //이번 자르는 방법을 진행했을 경우 토핑의 개수가 같다면 answer를 증가시킵니다.
            if(leftCnt==rightCnt) answer++;
        }
        
        //답을 반환합니다.
        return answer;
    }
    
    //해당 배열의 토핑 개수를 세는 함수 count 입니다.
    static int count (int[] arr){
        
        //결과 값을 담을 result 배열입니다.
        int result = 0;
        
        //주어진 arr배열을 돌며 i번째 수가 0보다 크다면 result를 증가시킵니다.
        for(int i=0; i<arr.length; i++){
            if(arr[i]>0) result++;
        }
        
        //결과를 반환합니다.
        return result;
    }
}