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

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

프로그래머스

---

문제 풀이

HashMap, HashSet을 같이 사용하여 시간 복잡도를 줄였다.

import java.util.*;

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