[JAVA 문제 풀이] 414. Fruits Into Baskets III

Fruits Into Baskets III - LeetCode

Can you solve this real interview question? Fruits Into Baskets III - You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket. From left to right, place the fruits according to these rules: * Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type. * Each basket can hold only one type of fruit. * If a fruit type cannot be placed in any basket, it remains unplaced. Return the number of fruit types that remain unplaced after all possible allocations are made.   Example 1: Input: fruits = [4,2,5], baskets = [3,5,4] Output: 1 Explanation: * fruits[0] = 4 is placed in baskets[1] = 5. * fruits[1] = 2 is placed in baskets[0] = 3. * fruits[2] = 5 cannot be placed in baskets[2] = 4. Since one fruit type remains unplaced, we return 1. Example 2: Input: fruits = [3,6,1], baskets = [6,4,7] Output: 0 Explanation: * fruits[0] = 3 is placed in baskets[0] = 6. * fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7. * fruits[2] = 1 is placed in baskets[1] = 4. Since all fruits are successfully placed, we return 0.   Constraints: * n == fruits.length == baskets.length * 1 <= n <= 105 * 1 <= fruits[i], baskets[i] <= 109

https://leetcode.com/problems/fruits-into-baskets-iii/

과일과 바구니라는 두 개의 정수 배열이 주어지는데,
각각의 길이 n은 과일의 i번째 유형의 양을 나타내고,
바구니[j]는 j번째 바구니의 용량을 나타냅니다.

왼쪽에서 오른쪽으로 과일을 다음 규칙에 따라 배치하세요:

* 각 과일 종류는 해당 과일 종류의 양보다 크거나 같은 용량으로 가장
  왼쪽에 있는 바구니에 넣어야 합니다.
* 각 바구니에는 한 가지 종류의 과일만 담을 수 있습니다.
* 과일 종류를 바구니에 넣을 수 없는 경우, 그대로 둡니다.

가능한 모든 할당이 완료된 후에도 배치되지 않은 과일 종류의 수를 반환합니다.

다른 사람의 코드 + 내가 공부한 코드

class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = baskets.length; // 바구니 개수 (즉, 과일 개수와 같음)
        int N = 1; // 세그먼트 트리용 배열 크기의 기준
        while (N <= n) N <<= 1; // N을 바구니 개수 이상인 2의 거듭제곱으로 설정 (세그먼트 트리 용도)
    
        int[] segTree = new int[N << 1]; // 세그먼트 트리 배열 (크기: 2 * N)

        // 리프 노드에 바구니 용량 초기화
        for (int i = 0; i < n; i++)
            segTree[N + i] = baskets[i]; // 리프 노드 위치에 바구니 용량 삽입

        // 내부 노드를 계산해 세그먼트 트리 완성
        for (int i = N - 1; i > 0; i--) 
            segTree[i] = Math.max(segTree[2 * i], segTree[2 * i + 1]); // 자식 노드 중 최대값을 부모 노드에 저장
        
        int count = 0; // 담지 못한 과일 개수 카운트

        for (int i = 0; i < n; ++i) {
            int x = fruits[i]; // 현재 과일의 무게

            int index = 1; // 루트 노드부터 탐색 시작

            if (segTree[index] < x) { // 트리 전체에서 가장 큰 바구니도 과일보다 작으면
                count++; // 해당 과일은 담을 수 없으므로 카운트 증가
                continue; // 다음 과일로 넘어감
            }

            // 과일을 담을 수 있는 바구니를 찾는 탐색
            while (index < N) { // 리프 노드에 도달할 때까지 반복
                if (segTree[index * 2] >= x) // 왼쪽 자식이 과일을 담을 수 있다면
                    index *= 2; // 왼쪽으로 이동
                else
                    index = index * 2 + 1; // 아니면 오른쪽으로 이동
            }

            segTree[index] = -1; // 해당 바구니는 사용했으므로 -1로 처리

            // 부모 노드 갱신: 위로 올라가며 트리 값을 다시 계산
            while (index > 1) {
                index >>= 1; // 부모 노드로 이동
                segTree[index] = Math.max(segTree[2 * index], segTree[2 * index + 1]); // 자식 중 최대값으로 갱신
            }
        }

        return count; // 담지 못한 과일의 총 개수 반환
    }
}

Segment Tree - stupefyee

(세그먼트 트리) | 기술정리

https://stupefyee.inblog.io/segment-tree-64967?traffic_type=internal