[level2] 롤케이크 자르기 JAVA

 

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

---

문제해석

- 롤케이크 위에 토핑 배열이 나란히 올려져 있다. 롤케이크를 잘라서 동생과 형이 나누어 먹는데 토핑 종류의 수로 나눈다.

    즉 1차원 배열 안에 들어가 있는 토핑 종류의 수를 똑같이 나누는 것!

---

 

1. 첫번째 시도

- HashMap을 이용하면 되는 문제라고 생각했다 -> 시간 초과!!!

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        int n = 1;
        while(n < topping.length-1){
            HashMap<Integer, Integer> map1 = new HashMap<>();
            HashMap<Integer, Integer> map2 = new HashMap<>();
            for(int i = 0; i < n; i++){
                map1.put(topping[i], 0);
            }
            
            for(int i = n; i < topping.length; i++){
                if(map1.size() < map2.size()){
                    break;
                }
                map2.put(topping[i], 0);
            }
            
            if(map1.size() == map2.size()) {
                answer++;
            }
            n++;
        }
         
        return answer;
    }
}

 

 

2. 두번째 시도

- 1번에서 시간 초과가 나온 것은 동일한 배열에서 1개씩 옆으로 넘기면 되는 문제인데,

  계속 hashmap을 만들고 넣고를 반복해서~~!! -> 문제를 너무 1차원 적으로 풀려고한다. 컬렉션 사용의 효율을 좀 더 고민!!

-> 먼저 HashMap에 배열을 다 넣어준뒤, 1개씩을 HashSet에 옮긴다. 그리고 둘의 사이즈를 비교한다.

    서로 다른 컬렉션을 사용하는 이유는 옆으로 넘길 때 남아있는 토핑의 갯수를 확인해야 하기 때문에! 0이면 종류에서 X

 

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        //롤케이크 토핑의 종류를 hashMap에 다 넣기
        HashMap<Integer, Integer> hm = new HashMap<>();
        HashSet<Integer> hs = new HashSet<>();
        for(int i = 0; i < topping.length; i++){
            hm.put(topping[i], hm.getOrDefault(topping[i], 0)+1);
        }
        
        for(int i = 0; i < topping.length-1; i++){
            int tmp = topping[i];
            //hs 넣고, hm엔 빼고
            if(!hs.contains(tmp)) hs.add(tmp);
            hm.put(tmp, hm.getOrDefault(topping[i], 0)-1);
            if(hm.get(tmp) == 0){
                hm.remove(tmp);
            }
            if(hm.size() == hs.size()) answer++;
        }
        return answer;
    }
}