[Java] 프로그래머스 Lv2 - 롤케이크 자르기

 

방법1. HashMap

import java.util.HashMap;

class Solution {
    public int solution(int[] topping) {
        HashMap<Integer, Integer> aMap = new HashMap<>();
        HashMap<Integer, Integer> bMap = new HashMap<>();
        int aCake = 0;
        int bCake = 0;
        int answer = 0;

        for(int i=0; i<topping.length; i++) {
            bMap.put(topping[i], bMap.getOrDefault(topping[i], 0) + 1);
            if(bMap.get(topping[i]) == 1) bCake++;
        }

        for(int i=0; i<topping.length; i++) {

            if(aMap.containsKey(topping[i])) {
                aMap.replace(topping[i], aMap.get(topping[i]) + 1);
            } else {
                aMap.put(topping[i], 1);
                aCake++;
            }

            int bValue = bMap.get(topping[i]);
            bMap.put(topping[i], bValue - 1);
            if(bValue - 1 == 0) bCake--;

            if(aCake == bCake) answer++;
        }

        return answer;
    }
}

 

 

방법2. 2차원 배열

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

        for (int j : topping) {
            if (sep[j][1] == 0) {
                bCake++;
            }
            sep[j][1]++;
        }

        for(int i : topping) {
            if (sep[i][0] == 0) {
                aCake++;
            }
            sep[i][0]++;
            sep[i][1]--;

            if (sep[i][1] == 0) {
                bCake--;
            }

            if(aCake == bCake) {
                answer++;
            }
        }
        return answer;
    }
}

 

2차원배열로 풀었을 때 많은 속도향상을 이루어내었다