롤케이크 자르기

ㅇ 문제설명

 

 

ㅇ 처음 푼 방법

public static int solution(int[] topping) {
        HashSet<Integer> totalTypes = new HashSet<>();
        for (int type : topping) {
            totalTypes.add(type);
        }
        int totalCount = totalTypes.size();
        int waysToSplit = 0;

        HashSet<Integer> leftTypes = new HashSet<>();
        HashSet<Integer> rightTypes = new HashSet<>();

        for(int type : topping){
            rightTypes.add(type);
        }

        for(int i = 0; i < topping.length-1; i++){
            leftTypes.add(topping[i]);
            rightTypes.remove(topping[i]);

            if(leftTypes.size() == rightTypes.size() && leftTypes.size() * 2 == totalCount){

                waysToSplit++;
            }
        }
        return waysToSplit;
    }

이랬는데, topping이 1,2,3,1,4로 주어질때,

두번째 for문에서 i가 1일때, leftTypes에는 1,2 rightTypes에는 3,4일때 waysToSplit이 1이 되어 실패했다.

다시 보니, leftTypes와 righTypes를 비교하는게 아니라, 나누는 기준이 잘못됐다.

처음에 totalTypes를 구할 필요없이,

ArrayList로 왼쪽, 오른쪽을 나누는 모든 경우의 수를 보고, 그 경우의 수에 왼쪽, 오른쪽 타입의 개수를 구한뒤, 그게 같아지는 경우의수만 count 해주면 되는것이었다. 쉬운걸 너무 어렵게 돌아서 생각했다.

 

ㅇ 두번째 방법

public static int solution(int[] topping) {
        int waysToSplit = 0;

        for (int i = 1; i < topping.length; i++) { 
            ArrayList<Integer> leftList = new ArrayList<>();
            ArrayList<Integer> rightList = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                leftList.add(topping[j]);
            }
            for (int j = i; j < topping.length; j++) {
                rightList.add(topping[j]);
            }

            HashSet<Integer> leftSet = new HashSet<>(leftList);
            HashSet<Integer> rightSet = new HashSet<>(rightList);
            
            if (leftSet.size() == rightSet.size()) {
                waysToSplit++;
            }
        }

        return waysToSplit;
    }

이렇게 해주면 topping이 1,2,3,1,4 로 주어진다고 생각해보자.

i가 1일때,

leftList는 1, rightList는 2,3,1,4로 주어지고

leftList와 rightList의 토핑종류의 수를각각 구해서 같아질때, waysToSplit을 더해준다.

그렇게 되면 일단은 예시는 다 적용이 된다.

 

하.지.만

시간초과가 뜬다. 역시 정답률이 괜히 낮은게 아니었다.

역시 모든 경우의수를 구하는게 아닌가? 싶었다.

 

ㅇ 정답 코드

public int solution(int[] topping) {
        HashMap<Integer, Integer> totalCount = new HashMap<>();
        HashMap<Integer, Integer> leftCount = new HashMap<>();
        int distinctTotal = 0, distinctLeft = 0, waysToSplit = 0;

        // 전체 토핑 개수 카운팅
        for (int t : topping) {
            totalCount.put(t, totalCount.getOrDefault(t, 0) + 1);
        }
        distinctTotal = totalCount.size();

        for (int i = 0; i < topping.length - 1; i++) {
            int currentTopping = topping[i];
            leftCount.put(currentTopping, leftCount.getOrDefault(currentTopping, 0) + 1);
            // 왼쪽 조각에 토핑이 처음 추가되는 경우
            if (leftCount.get(currentTopping) == 1) {
                distinctLeft++;
            }
            // 오른쪽 조각에서 해당 토핑이 완전히 사라지는 경우
            totalCount.put(currentTopping, totalCount.get(currentTopping) - 1);
            if (totalCount.get(currentTopping) == 0) {
                distinctTotal--;
            }

            // 왼쪽과 오른쪽 조각의 고유한 토핑 개수가 같은 경우
            if (distinctLeft == distinctTotal) {
                waysToSplit++;
            }
        }

        return waysToSplit;
    }

HashMap을 사용해서 이중for문이 아니라 반복문 한개로 기준에 해당하는 경우의수를 체크한다.

솔직히 너무 어렵다.