프로그래머스: 롤케이크 자르기(JAVA)

🧩 문제 설명

철수는 동생에게 롤케이크의 절반을 공평하게 나눠주려고 합니다.

• 롤케이크에는 여러 종류의 토핑이 순서대로 놓여 있고,
• 철수는 토핑이 놓인 순서대로 한 조각씩 왼쪽으로 자를 수 있습니다.
• 이때 자신과 동생이 갖게 되는 토핑의 종류 수가 같아지는 경우의 수를 구해야 합니다.

❗예시

입력: [1, 2, 1, 3, 1, 4, 1, 2]
출력: 2

 

---

풀이방법

1. 전체 토핑 개수를 Map으로 세어둔다.
2. 왼쪽부터 한 칸씩 자르면서:
   • 왼쪽 토핑 종류는 Set으로 관리하고,
   • 오른쪽 토핑 종류는 Map에서 하나씩 감소시키며 관리합니다.
3. 양쪽의 토핑 종류 수(Set.size() vs Map.size())가 같으면 answer 증가

---

JAVA 코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        Map<Integer, Integer> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();

        // 1. 전체 토핑의 개수를 센다
        for (int i = 0; i < topping.length; i++) {
            map.put(topping[i], map.getOrDefault(topping[i], 0) + 1);
        }

        // 2. 한 칸씩 자르면서 비교
        for (int i = 0; i < topping.length; i++) {
            int num = topping[i];

            set.add(num); // 왼쪽에 추가
            map.put(num, map.get(num) - 1); // 오른쪽에서 제거

            if (map.get(num) == 0) {
                map.remove(num); // 수가 0이 되면 제거
            }

            // 양쪽 토핑 종류 수가 같으면 정답++
            if (set.size() == map.size()) {
                answer++;
            }
        }

        return answer;
    }
}

 

포인트

오른쪽 토핑 종류 개수 관리 -> Map

왼쪽 토핑의 종류 추적 ->Set

 

👉 이런 문제에서는 "종류 수" = Set/Map size 를 떠올리는 습관이 중요.

 

시간복잡도

O(N)
전체 배열을 두 번 순회하므로 선형 시간 복잡도로 효율적