Programmers 132265 - 롤케이크 자르지

코딩테스트 연습 - 롤케이크 자르기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

조각마다 동일한 가짓수의 토핑이 올라가 있으면 공평하게 나누어진 것이다.

→ 토핑의 개수보다는 가짓수가 중요하다.

롤 케이크를 공평하게 자르는 방법의 수를 구하시오.

전체 토핑을 관리하며 포인트를 이동시켜 가며 확인을 한다.

1. 토핑 종류 : 개수 Map으로 기록
2. 포인터를 0부터 오른쪽으로 이동시켜한다.
3. 해당 포인터의 토핑을 Map 에서 1개 뺀다. 만약 개수가 0이 되면 제거한다.
4. 현재 내 토핑은 Set을 통해 관리한다.
5. 최종적으로 내 토핑 set과 전체 토핑 map의 크기가 같으면 공평한 것이다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        Map<Integer, Integer> toppings = new HashMap<>();
        Set<Integer> myToppings = new HashSet<>();
        int answer = 0;
        
        for (int t : topping) {
            toppings.put(t, toppings.getOrDefault(t, 0) + 1);
        }
        
        for (int i = 0; i < topping.length; i++) {
            int t = topping[i];
            myToppings.add(t);
            toppings.put(t, toppings.get(t) - 1);
            if (toppings.get(t) == 0) {
                toppings.remove(t);
            }
            
            if (myToppings.size() == toppings.size()) {
                answer++;
            }
        }
        return answer;
    }
}