[Java] Lv.2 롤케이크 자르기

문제

문제 풀이

생각보다 단순했다.

그냥 각 인원의 토핑 종류를 저장할 배열을 각각 만들고

한 쪽에 일단 전부 몰아준 뒤에 하나씩 다른쪽에 넘겨주면서 토핑 종류를 비교하면 쉽다.

자바 코드

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        // 토핑 종류
        int toppingKind = Arrays.stream(topping).max().getAsInt();
        
        // 각 인원이 가진 토핑 개수를 기록할 배열, 1 ~ toppingKind만큼의 수를 위해 toppingKind + 1
        // 추가로 마지막에 가진 토핑 종류가 몇개인지 기록하기 위한 +1 해서 총 toppingKind + 2 갯수의 배열
        int[] t1 = new int[toppingKind + 2];
        int[] t2 = new int[toppingKind + 2];
        
        // 첫 토핑을 철수에게
        // 가진 토핑 종류도 +1
        t1[topping[0]]++;
        t1[t1.length - 1]++;
        
        // 나머지는 일반 동생에게 준다.
        for(int i = 1; i < topping.length; i++){
            // 동생이 가진 토핑이 처음 가지는 것이라면 가진 종류 +1
            if(t2[topping[i]] == 0)
                t2[t2.length - 1]++;
            
            // 토핑 갯수 +1
            t2[topping[i]]++;
        }
        
        // 철수와 동생의 가진 토핑 종류 갯수가 같다면 정답 +1
        if(t1[t1.length - 1] == t2[t1.length - 1])
            answer++;
        
        // 동생이 가진 토핑을 하나씩 철수에게 줘가면서 토핑 종류 갯수를 비교한다.
        for(int i = 1; i < topping.length; i++){
            // 철수가 토핑을 하나 동생에게서 가져간다.
            // 처음 갖는 종류의 토핑일 경우 종류의 수 +1
            if(t1[topping[i]] == 0)
                t1[t1.length - 1]++;
            
            t1[topping[i]]++;
            
            // 동생이 토핑을 하나 철수에게 줄 때 해당 종류의 토핑을 더 이상 가지고 있지 않다면
            // 토핑 종류의 수 -1
            if(t2[topping[i]] - 1 == 0)
                t2[t2.length - 1]--;
            
            t2[topping[i]]--;
            
            // 하나 넘겨줄 때마다 두 사람의 토핑 종류 개수를 비교한다.
            if(t1[t1.length - 1] == t2[t1.length - 1])
                answer++;
        }
        
        return answer;
    }
}