[Java] 프로그래머스(level-2) - 롤케이크 자르기

문제 풀이

---

이번 문제는 문제에서 요구한 대로 자료구조를 잘 활용하여 구현하면 되는 문제이다.

아이디어 도출

이 문제에서는 철수와 동생이 동일한 토핑 수를 나눠 먹을 수 있도록 롤케이크를 자를 수 있는 경우를 반환해야 한다. 어떤 자료구조를 이용할 수 있을까?

• HashMap
• HashSet

필자는 위 2개의 자료구조를 이용해 형과 동생이 나눠먹을 토핑 수를 기록하고 비교하여 롤케이크를 자를 수 있는지 비교하였다.

또한, 배열의 길이는 최대 1,000,000까지 주어질 수 있어 시간초과를 고려해야 한다. 그래서 O(n)의 시간복잡도를 맞출 수 있도록 하였다.

1. topping 배열을 순회하며 원소를 key로, 원소의 빈도 수를 value로 Map에 삽입한다.
2. 다시 topping 배열을 순회하며, 등장하는 원소마다 Set에 삽입하고 Map에서는 해당 원소의 빈도 수를 1씩 차감한다.
3. 2번 과정을 마친 후, 만약 Map에서 해당 원소의 빈도 수가 0이라면 Map에서 해당 원소를 제거한다.
4. 이후, Map과 Set의 크기가 같다면, 같은 토핑 수를 보유하고 있는 것이기에 롤 케이크를 자를 수 있다고 판단하여 answer를 1 증가시킨다.

중복이 허용되지 않는 HashSet을 통해 HashMap과의 크기 비교를 통해 같은 토핑 수를 유지하고 있는지를 확인할 수 있다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    public int solution(int[] topping) {
        
        HashMap<Integer, Integer> hm = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();

        // map에 원소와 빈도 수를 key:value로 담는다.
        for(int ele : topping) {
            hm.put(ele, hm.getOrDefault(ele, 0)+1);
        }
        
        int answer = 0;

        /**
         * set에 해당 원소를 담은 후, map에서 빈도 수를 1씩 차감한다.
         * 만약 map의 빈도 수가 0이면 map에서 제거한다.
         * set과 map의 크기가 같다면 같은 토핑 수를 보유하기에 answer를 1 증가시킨다.
         */
        for(int ele : topping) {
            hm.put(ele, hm.getOrDefault(ele, 0)-1);
            set.add(ele);

            if(hm.get(ele) == 0) {
                hm.remove(ele);
            }

            if(hm.size() == set.size()) {
                answer++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        
        Solution sol = new Solution();
        int[] topping = new int[]{1, 2, 1, 3, 1, 4, 1, 2};
        
        sol.solution(topping);

    }

}

회고

-

---

출처

-

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.