[Programmers] 롤케이크 자르기

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

프로그래머스

문제 설명

형과 동생이 토핑의 개수를 똑같이 나눠먹기 위한 문제이다. 문제를 보고 Set을 사용해서 풀려고 했으나 엄청난 시간 초과를 보았고 Map과 Set을 함께 사용하여 해결했다.

코드

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;

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

Set만 사용해서 풀었던 코드

최대 크기가 1,000,000(백만)인데 매번 모든 요소를 순회했다. 따라서 토핑이 백만 개라면 백만*백만만큼의 시간복잡도가 되므로 시간 초과가 발생했다.

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int[] toppings) {
        int answer = 0;
        
        for (int i = 0; i < toppings.length; i++) {
            Set<Integer> older = new HashSet<>();
            Set<Integer> younger = new HashSet<>();
            
            for (int j = 0; j < i; j++) {
                older.add(toppings[j]);
            }
            
            for (int j = i; j < toppings.length; j++) {
                younger.add(toppings[j]);
            }
            
            if (older.size() == younger.size()) {
                answer++;
            }
        }
        
        return answer;
    }
}