프로그래머스 롤케이크 자르기 자바 풀이

문제 링크

문제 요약

topping 배열은 롤케이크에 일렬로 올라간 토핑 번호다
한 지점을 잘라 두 조각으로 나눴을 때, 양쪽 토핑 종류 수가 같아야 공평하게 나눈 것이다
공평하게 자를 수 있는 방법의 수를 구하는 문제다

문제 풀이

처음에는 자르는 위치마다 왼쪽과 오른쪽 배열을 나눠서 각각 서로 다른 토핑 종류를 세면 되겠다고 생각했다.

하지만 topping의 길이가 최대 1,000,000인데, 자를 수 있는 위치도 그만큼 많다.

매 위치마다 왼쪽과 오른쪽을 처음부터 다시 세면 위치 하나당 O(n)이 걸리고, 이를 모든 위치에 대해 반복하면 O(n²)이 되어 시간 초과가 난다.

이 문제의 핵심은 자르는 위치를 하나씩 오른쪽으로 옮길 때, 토핑 하나가 오른쪽에서 왼쪽으로 넘어가는 것뿐이라 종류 수를 처음부터 다시 셀 필요가 없다는 점이다.

먼저 오른쪽 카운트 배열을 topping 전체로 채워서, 전체가 오른쪽에 있는 상태에서 시작한다
왼쪽으로 하나씩 옮기면서, 그 토핑이 왼쪽에 처음 등장하면 leftKinds를 늘리고, 오른쪽에서 그 토핑이 완전히 사라지면 rightKinds를 줄인다
옮긴 직후 leftKinds와 rightKinds가 같으면 그 자리가 공평한 절단선이므로 answer를 늘린다

마지막 토핑을 옮기고 나면 오른쪽 조각이 비어버리므로, 반복은 topping.length - 1까지만 돈다.

최종 코드

java

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int[] rightCount = new int[10001]; // 오른쪽 조각에 남은 토핑별 개수
        boolean[] leftHas = new boolean[10001]; // 왼쪽 조각에 등장한 적 있는 토핑

        int rightKinds = 0;
        int leftKinds = 0;

        // 처음에는 전체 토핑이 오른쪽 조각에 있는 상태로 시작
        for (int t : topping) {
            if (rightCount[t] == 0) {
                rightKinds++;
            }
            rightCount[t]++;
        }

        for (int i = 0; i < topping.length - 1; i++) {
            int t = topping[i];

            // 토핑 하나를 왼쪽으로 옮긴다
            if (!leftHas[t]) {
                leftHas[t] = true;
                leftKinds++;
            }

            rightCount[t]--;

            if (rightCount[t] == 0) {
                rightKinds--;
            }
            if (leftKinds == rightKinds) {
                answer++;
            }
        }

        return answer;
    }
}

롤케이크 자르기

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

할인 행사

숫자 변환하기

두 원 사이의 정수 쌍