Lv.2 롤케이크 자르기 [JAVA]

문제링크

문제 설명

철수는 롤케이크를 두 조각으로 잘라서 동생과 나눠 먹으려 한다.
케이크 위에는 여러 가지 토핑들이 일렬로 올려져 있으며, 크기나 개수가 아니라 토핑의 종류 수가 같을 때 공평하게 나눈 것으로 본다.

예를 들어 토핑이 [1, 2, 1, 3, 1, 4, 1, 2]라면, 4번째(3)와 5번째(1) 사이에서 자르면

• 왼쪽: [1, 2, 1, 3] → {1, 2, 3} → 3가지
• 오른쪽: [1, 4, 1, 2] → {1, 2, 4} → 3가지
  따라서 공평하게 나눈 경우가 된다.

롤케이크를 공평하게 나누는 방법의 수를 구하는 문제이다.

성공 여부(걸린시간): 성공(15분 14초)

아이디어

• 오른쪽 조각의 상태를 HashMap으로 관리한다. (토핑별 개수)
• 왼쪽 조각은 HashSet으로 관리한다. (종류만 중요)
• 처음에는 모든 토핑이 오른쪽에 있으므로 HashMap을 채운다.
• 순차적으로 토핑을 하나씩 왼쪽으로 옮기면서
  • 왼쪽은 HashSet.add()
  • 오른쪽은 HashMap에서 개수 줄이고, 0이 되면 제거
• 매 단계마다 left.size() == right.size()면 공평하게 나눈 경우이므로 answer++

시간 복잡도는 O(N), 각 토핑을 한 번씩만 처리하면 된다.

풀이코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        HashMap<Integer, Integer> right = new HashMap<>();
        HashSet<Integer> left = new HashSet<>();

        // 초기: 오른쪽에 모든 토핑 저장
        for (int top : topping) {
            right.put(top, right.getOrDefault(top, 0) + 1);
        }

        // 하나씩 왼쪽으로 이동
        for (int top : topping) {
            // 공평한 순간 체크
            if (left.size() == right.size()) {
                answer++;
            }

            // 왼쪽에 추가
            left.add(top);

            // 오른쪽에서 제거 or 감소
            if (right.get(top) == 1) {
                right.remove(top);
            } else {
                right.put(top, right.get(top) - 1);
            }
        }

        return answer;
    }
}