롤케이크 자르기_복습

2026.07.29

문제 풀이

나의 코드

---

소요 시간: 19분
시간 복잡도: $O(n)$

---

개선점

Integer t = topping[i];

의 과정에서 오토 언박싱이 지속적으로 발생함
int로 선언 후, put 시점에만 박싱되게 하는 것이 나음

---

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] topping) {
        int result = 0;
        Map<Integer, Integer> right = new HashMap<>();
        Map<Integer, Integer> left = new HashMap<>();
        
        for (int i = 0; i < topping.length; i++) {
            Integer t = topping[i];
            right.put(t, right.getOrDefault(t, 0) + 1);
        }
        for (int i = 0; i < topping.length; i++) {
            Integer t = topping[i];
            left.put(t, left.getOrDefault(t, 0) + 1);
            right.put(t, right.get(t) - 1);
            if (right.get(t) <= 0) {
                right.remove(t);
            }
            if (left.size() == right.size()) {
                result++;
            }
        }
        return result;
    }
}

AI 코드

---

시간 복잡도: $O(n)$

---

코드 분석

right는 개수가 계속 빠지므로 rightCnt를 사용하고,

left는 개수가 빠지지 않으므로,
leftHas를 이용하여 이미 가지고 있던 토핑인지 구분한다.

---

class Solution {
    public int solution(int[] topping) {
        int[] rightCnt = new int[10001];
        boolean[] leftHas = new boolean[10001];
        int leftKind = 0, rightKind = 0, answer = 0;

        for (int t : topping) {
            if (rightCnt[t]++ == 0) rightKind++;
        }

        // i번째까지 철수, 나머지 동생 → 마지막 인덱스는 자를 수 없으므로 제외
        for (int i = 0; i < topping.length - 1; i++) {
            int t = topping[i];
            if (--rightCnt[t] == 0) rightKind--;
            if (!leftHas[t]) {
                leftHas[t] = true;
                leftKind++;
            }
            if (leftKind == rightKind) answer++;
        }
        return answer;
    }
}

문제 풀이 후기

배열의 길이가 1,000,000 이하인 조건을 보고, 2중 반복문을 사용하면 안된다는 것을 이전의 문제를 풀면서 알아냈다.

이전에는 고려하지 않고 일단 코드 작성 뒤 시간 초과 오류가 났을 부분이지만,
이전과는 달리 한 번에 통과하여 발전하고 있는 자신이 보기 좋다.