Lv 2. 롤케이크 자르기

 

처음 떠올린 자료구조는 Set 이었다. 중복 제거를 통해 토핑의 갯수를 파악 할 수 있을 것이라 생각했고 어차피 2명이서 나눠 먹는것이라면 토핑의 갯수는 같을 것이고 전체 토핑의 갯수에서 짝수일때는 2분의 1이며 홀수일 때는 2분 의 1에서 하나를 더한값과 같을것이라 생각하여 코드를 구상하였다.

하지만 홀수 일때 중간에 단하나의 다른 토핑이 있을 때 오류가 발생 하였고 이를 해결하지 못할 것 같아 엎어 보았다.

모든 토핑의 종류와 갯수를 Map에 저장하고 하나씩 짚어가며 앞롤케잌에서는 ++ 뒷롤케잌에서는 --를 진행하여 두개의 케이크의 토핑갯수가 같을 때 answer을 구한다는 부분은 같으나 

Map을 사용하였는가 array를 사용하였는가에 따른 효율차이가 매우 극심하였다. Map과 Set을 이용하여 푼 코드는 효율적이지 못한것으로 판단하여 다른사람의 코드를 참조하여 풀어내었다.

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int[][] log  = new int[2][10001];

        for(int cur : topping){
            if(log[0][cur]==0) log[0][0]++;
            log[0][cur]++;
        }
        
        for(int cur : topping){
            log[0][cur]--;
            if(log[0][cur]==0) log[0][0]--;
            if(log[1][cur]==0) log[1][0]++;
            log[1][cur]++;
            if(log[0][0] == log[1][0]) answer++;
        }
        return answer;
    }
}

 

그결과 시간복잡도 측면에서 성과를 거둘 수 있었다.