[프로그래머스][JAVA][Lv. 2] 롤케이크 자르기

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.Queue;
import java.util.HashSet;
import java.util.HashMap;
import java.util.LinkedList;

class Solution {
    public int solution(int[] topping) {
        HashMap<Integer, Queue<Integer>> toppingMap = new HashMap<>();
        HashSet<Integer> leftSet = new HashSet<>();
        HashSet<Integer> rightSet = new HashSet<>();
        int answer = 0;
        
        for (int i = 0; i < topping.length; i++) {
            if (!toppingMap.containsKey(topping[i])) {
                Queue<Integer> temp = new LinkedList<>();
                toppingMap.put(topping[i], temp);
                temp.add(i);
            }
            else toppingMap.get(topping[i]).add(i);
            rightSet.add(topping[i]);
        }
        
        for (int i = 0; i < topping.length; i++) {
            if (toppingMap.get(topping[i]).size() == 1) {
                rightSet.remove(topping[i]);
                leftSet.add(topping[i]);
            }
            else {
                toppingMap.get(topping[i]).poll();
                leftSet.add(topping[i]);
            }
            if (leftSet.size() == rightSet.size()) answer++;
        }
        
        return answer;
    }
}

---

후기

문제가 원하는 것은 피자를 반으로 나누되 토핑 종류의 수만 같으면 되므로 가상으로 왼쪽과 오른쪽으로 구분하여 중복을 가질 수 없는 Set을 이용하여 수를 비교할 수 있도록 했다. 처음 for문은 일단 Map의 값인 Queue로 각 토핑의 종류의 수를 저장할 수 있도록 했고(사실 이부분에서 index를 저장하는 것이 아닌 Queue 대신 Integer로 카운트를 저장해도 상관없다. 사실 이 방법이 더 효율적이다. 근데 다 풀고 나서 생각이 났다...) 두 번째 for문에서 오른쪽에 1개 초과의 토핑의 있을 경우 하나씩 빼서 개수를 줄였다. 1개가 되면 오른쪽에는 토핑이 더이상 없다는 의미이므로 오른쪽 Set에서 해당 토핑을 지운다.