[Algorithm][LeetCode 3477][Easy] Fruits Into Baskets II

문제 설명

두 개의 배열 fruits, baskets가 주어집니다.

• fruits[i]: i번째 과일의 수량
• baskets[j]: j번째 바구니의 용량

다음 조건에 따라 과일을 왼쪽에서 오른쪽 방향으로 바구니에 담습니다.

1. 각 과일은 자신보다 크거나 같은 용량을 가진 바구니 중 가장 왼쪽에 있는 바구니에 들어갈 수 있습니다.
2. 각 바구니에는 한 종류의 과일만 담을 수 있습니다.
3. 들어갈 수 있는 바구니가 없다면, 해당 과일은 남겨집니다.

반환값: 바구니에 들어가지 못한 과일의 개수

 

---

 

예시

// 예시 1
입력: fruits = [4, 2, 5], baskets = [3, 5, 4]
설명:
- fruits[0] = 4 → baskets[1] = 5에 배치
- fruits[1] = 2 → baskets[0] = 3에 배치
- fruits[2] = 5 → baskets[2] = 4 (수용 불가 → 배치 실패)
결과: 1

// 예시 2
입력: fruits = [3, 6, 1], baskets = [6, 4, 7]
설명:
- fruits[0] = 3 → baskets[0] = 6에 배치
- fruits[1] = 6 → baskets[2] = 7에 배치
- fruits[2] = 1 → baskets[1] = 4에 배치
결과: 0

 

---

 

접근 방법

1. 과일 배열을 왼쪽부터 순회
2. 각 과일에 대해, 바구니 배열을 왼쪽부터 순회하며 다음 조건을 만족하는 바구니를 찾음:
   • 아직 사용되지 않았고
   • 바구니 용량이 과일 수량보다 크거나 같음
3. 조건을 만족하면 해당 바구니를 사용 처리
4. 모든 바구니를 탐색했는데도 배치하지 못하면, 해당 과일은 남게 됨

 

---

 

주의할 점

• 바구니는 오직 한 번만 사용할 수 있으므로, 사용 여부를 별도로 추적해야 합니다.
• 시간 복잡도는 O(n²)로, n ≤ 100이므로 성능에 큰 문제는 없습니다.
• Set 또는 객체를 활용해 사용된 바구니를 추적할 수 있습니다.

 

---

 

JavaScript 코드

/**
 * @param {number[]} fruits
 * @param {number[]} baskets
 * @return {number}
 */
var numOfUnplacedFruits = function(fruits, baskets) {
    const usedBaskets = new Set();  // 사용된 바구니 인덱스를 추적
    let placed = 0;

    for (let i = 0; i < fruits.length; i++) {
        for (let j = 0; j < baskets.length; j++) {
            if (!usedBaskets.has(j) && baskets[j] >= fruits[i]) {
                usedBaskets.add(j);  // 바구니 사용 처리
                placed++;
                break;
            }
        }
    }

    return fruits.length - placed;  // 배치되지 못한 과일 개수 반환
};

 

---

 

잘못된 접근: basketIndex 포인터 방식

풀이가 2중 for문으로 구현되어, 좀 더 최적화할 수 있는 방법을 찾아보다가, 바구니 위치를 포인터로 기억하는 방식을 사용해보았습니다.

그러나, 이 방식을 사용하게 될 경우, 문제의 조건을 위반하게 됩니다.

var numOfUnplacedFruits = function(fruits, baskets) {
    const used = new Array(baskets.length).fill(false);
    let basketIndex = 0;
    let placed = 0;

    for (let i = 0; i < fruits.length; i++) {
        while (basketIndex < baskets.length) {
            if (!used[basketIndex] && baskets[basketIndex] >= fruits[i]) {
                used[basketIndex] = true;
                placed++;
                basketIndex++;
                break;
            }
            basketIndex++;
        }
    }

    return fruits.length - placed;
};

 

문제점

• basketIndex는 한 번 오른쪽으로 이동하면 되돌아갈 수 없음
• 따라서, 뒤에 나오는 큰 과일이 앞쪽에 남아 있던 더 큰 바구니를 사용하지 못함

 

반례로 이해하기

fruits =  [3, 2, 5]
baskets = [5, 3, 4]

 

올바른 배치 (왼쪽부터 탐색)

• fruit 3 → basket 1 (3) 사용
• fruit 2 → basket 2 (4) 사용
• fruit 5 → basket 0 (5) 사용
• → 전부 배치됨 → 정답: 0

 

basketIndex 방식

• fruit 3 → basket 0 (5) 사용
• fruit 2 → basket 1 (3) 사용
• fruit 5 → basket 2 (4) → 수용 불가 → 배치 실패
• → 정답: 1 (오답)

 

---

마무리

 

이 문제는 단순한 조건 기반 탐색이지만, 다음과 같은 점을 고려해야 했습니다.

 

• 조건 순서에 따라 왼쪽부터 바구니를 우선적으로 배치해야 함
• 한 번 사용된 바구니는 다시 사용할 수 없으므로 상태 추적 필요
• 구조는 단순하지만, 실수 없이 조건을 모두 만족하는 구현이 중요

 

추가로, 문제에서 “왼쪽부터 순차적으로 배치” 조건이 없었다면

바구니와 과일을 정렬한 후 최적 배치 알고리즘으로 더 효율적인 풀이도 가능했을 것입니다.

하지만 이 문제에서는 순서를 지키는 것이 핵심이기 때문에, 그 조건에 맞춘 탐색 로직이 필요했습니다.