롤케이크 자르기

작성일: 2024-11-08

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

접근 방식

케이크를 A와 B에게 나누어 준다고 했을 때, 먼저 B에게 모든 케이크를 주고 하나씩 A에게 넘겨주면서 케이크의 토핑 수를 고려했다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        Set<Integer> a = new HashSet<>();
        Set<Integer> b = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        int answer = 0;
        if(topping.length==1) return 0;
        for(int t:topping) {
            list.add(t);
            b.add(t);
        }
        for(int i=0; i<topping.length; i++){
            a.add(topping[i]);
            list.remove(Integer.valueOf(topping[i]));
            if(!list.contains(topping[i])) b.remove(topping[i]);
            if(a.size()==b.size()) answer++;
        }
        return answer;
    }
}

시간 초과가 발생했다.

최대 토핑 수가, 백만이기 때문에 list에 값을 넣고, 제거하는 과정에서 추가 연산이 발생하여 시간초과가 발생한 것으로 보인다.

시간 복잡도 O(n^2)

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        Map<Integer, Integer> a = new HashMap<>();
        Map<Integer, Integer> b = new HashMap<>();
        int answer = 0;
        if(topping.length==1) return 0;
        for(int t:topping) {
            b.put(t, b.getOrDefault(t, 0)+1);
        }
        for(int t:topping){
            a.put(t, a.getOrDefault(t, 0)+1); // A에 값 넣기
            b.put(t, b.get(t)-1);
            if(b.get(t)==0) b.remove(t);
            if(a.size()==b.size()) answer++;
        }
        return answer;
    }
}

값을 추가하고 제거하는 과정을 Map 자료구조를 사용하는 것으로 변경했다.

Map 자료구조에 대한 연산의 시간 복잡도는 O(1)이기에, 시간 복잡도는 O(n) 으로 최대 백 만번의 연산이 발생하여 시간초과가 발생하지 않았다.

느낀 점

일단 풀 수 있는 방법을 생각해보되, 주어진 환경에서 시간 초과가 발생할 수 있는 경우가 있는지를 좀 더 생각해보자