코딩 테스트 - 롤케이크 자르기

import java.util.Arrays;

class Solution {

    public static void main(String[] args) {

        int [] topping = {1, 2, 1, 3, 1, 4, 1, 2};

        solution(topping);

    }

    static int count = 0;

    public static int solution(int[] topping) {

       

        int halfCake = topping.length/2;

        int [] disTopping = Arrays.stream(topping).distinct().toArray();

        int disLength = disTopping.length/2; //토핑 나눠서 n개 되는지 확인

        System.out.println(disLength);

        System.out.println(halfCake+"기본반토막");

        int firstCake = cakeDivide(topping, halfCake);

       

        switch(firstCake){

            case 1:

                //같은 경우

                for(int i = halfCake-1; i > disLength; i--){

                    System.out.println("감소" + i);

                    System.out.println(cakeDivide(topping, i));                    

                }

               

                for(int i = halfCake+1; i < topping.length-disLength; i++){

                    System.out.println("증가" + i);

                    System.out.println(cakeDivide(topping, i));

                }

                break;

            case 2:

                //형이 더 많은 경우

                for(int i = halfCake-1; i > disLength; i--){

                    System.out.println("감소" + i);

                    System.out.println(cakeDivide(topping, i));

                   

                }

                break;

            case 3:

                //동생이 더 많은 경우

                for(int i = halfCake+1; i < topping.length-disLength; i++){

                    System.out.println("증가" + i);

                    System.out.println(cakeDivide(topping, i));

                }

                break;

        }

       

        return count;

    }

   

   

    public static int cakeDivide(int[] topping, int halfCake){

        //홀수일 경우 man1이 큼

        int [] man1 = Arrays.copyOfRange(topping, 0, halfCake);

        int [] man2 = Arrays.copyOfRange(topping, halfCake, topping.length);

        //반 자르고 시작

        int [] disman1 = Arrays.stream(man1).distinct().toArray();

        int [] disman2 = Arrays.stream(man2).distinct().toArray();

       

        if(disman1.length == disman2.length){

            //토핑 개수 같음

            count++;

            return 1;

        }else if(disman1.length > disman2.length){

            //형거 > 동생거

            return 2;

        }else{

            //동생거 > 형거

            return 3;

        }

    }

}

오늘도 슬픈 시간 초과...

다른 분 풀이 참고해서 풀고... Map이나 Set 안 쓴 코드 찾아봄

class Solution {

    public int solution(int[] topping) {

        int answer = 0;

       

        int [] man1 = new int[10001];

        int [] man2 = new int[10001];

       

        int man1s = 0;

        int man2s = 0;

       

        for(var i : topping){

            man1[i]++;

        }

        //topping의 해당 위치에 ++ 해줌

       

        for(var i : man1){

            man1s += i > 0 ? 1 : 0;

        }

        //값이 있으면 +1해줌

       

       

        for(var i : topping) {

            man1[i]--; //토핑 값 빼줌

            if (man1[i] == 0){

                man1s--;

            }

            if (man2[i] == 0) {

                man2s++;

            }

            man2[i]++; //토핑 값 더해줌

            if (man1s == man2s){

                answer++;

            }

        }

        return answer;

    }

}

똑똑박사!

근데 사실 그냥 애들이 반 나눠 먹었으면 좋겠다...

(_-_)