[JAVA 문제 풀이] 412. Fruit Into Baskets

Fruit Into Baskets - LeetCode

Can you solve this real interview question? Fruit Into Baskets - You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces. You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow: * You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold. * Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets. * Once you reach a tree with fruit that cannot fit in your baskets, you must stop. Given the integer array fruits, return the maximum number of fruits you can pick.   Example 1: Input: fruits = [1,2,1] Output: 3 Explanation: We can pick from all 3 trees. Example 2: Input: fruits = [0,1,2,2] Output: 3 Explanation: We can pick from trees [1,2,2]. If we had started at the first tree, we would only pick from trees [0,1]. Example 3: Input: fruits = [1,2,3,2,2] Output: 4 Explanation: We can pick from trees [2,3,2,2]. If we had started at the first tree, we would only pick from trees [1,2].   Constraints: * 1 <= fruits.length <= 105 * 0 <= fruits[i] < fruits.length

https://leetcode.com/problems/fruit-into-baskets/description/

당신은 왼쪽에서 오른쪽으로 배열된 한 줄의 과일 나무가 있는 농장을 방문하고 있습니다.
나무는 정수 배열의 과일로 표현되며, 여기서 과일[i]은 i번째 나무가 생산하는 과일의 종류입니다.

가능한 한 많은 과일을 수집하고 싶습니다.
그러나 소유자는 반드시 따라야 하는 몇 가지 엄격한 규칙이 있습니다:

* 바구니는 두 개뿐이며 각 바구니에는 단일 종류의 과일만 담을 수 있습니다.
  각 바구니에 담을 수 있는 과일의 양에는 제한이 없습니다.
* 원하는 나무에서 시작하여 오른쪽으로 이동할 때는
  각 나무(시작 나무 포함)에서 정확히 하나의 과일을 선택해야 합니다.
  선택한 과일은 바구니 중 하나에 넣어야 합니다.
* 바구니에 담을 수 없는 과일이 있는 나무에 닿으면 멈춰야 합니다.

정수 배열 과일이 주어지면, 선택할 수 있는 최대 과일 수를 반환하세요.

제약 사항:
* 1 <= fruits.length <= 105
* 0 <= fruits[i] < fruits.length

내가 작성한 코드

import java.util.*;

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> basket = new HashMap<>(); // 과일 종류, 개수
        int left = 0; // 슬라이딩 윈도우의 왼쪽 포인터
        int answer = 0;

        for (int right = 0; right < fruits.length; right++) { // 오른쪽 포인터 확장
            int curFruit = fruits[right]; // 현재 오른쪽 과일
            basket.put(curFruit, basket.getOrDefault(curFruit, 0) + 1); // 바구니에 추가

            while (basket.size() > 2) { // 바구니에 3종류 이상이면 줄이기
                int leftFruit = fruits[left]; // 왼쪽 과일
                basket.put(leftFruit, basket.get(leftFruit) - 1); // 개수 하나 줄이기

                if (basket.get(leftFruit) == 0) { // 0개 되면 종류 제거
                    basket.remove(leftFruit);
                }

                left++; // 왼쪽 포인터 이동
            }

            int windowLen = right - left + 1; // 현재 윈도우 길이
            answer = Math.max(answer, windowLen); // 최대 과일 수 갱신
        }

        return answer;
    }
}

다른 사람의 코드

class Solution {
    public int totalFruit(int[] fruits) {
        int[] count = new int[100001]; // 각 과일 종류의 개수를 저장하는 배열 (0~100000 범위)
        int left = 0; // 현재 슬라이딩 윈도우의 왼쪽 끝 인덱스
        int right = 0; // 현재 슬라이딩 윈도우의 오른쪽 끝 인덱스
        int max = 0; // 수확 가능한 과일의 최대 개수
        int types = 0; // 현재 윈도우 내의 과일 종류 수

        while (right < fruits.length) {
            // 새로운 과일 종류가 들어올 경우
            if (count[fruits[right]] == 0) {
                types++; // 과일 종류 수 증가
            }
            
            count[fruits[right]]++; // 해당 과일의 개수 증가
            right++; // 윈도우 오른쪽 확장

            // 과일 종류가 2개를 초과하면 왼쪽을 줄이며 조건 맞추기
            while (types > 2) {
                count[fruits[left]]--; // 왼쪽 과일 개수 감소
                if (count[fruits[left]] == 0) {
                    types--; // 해당 과일 종류가 윈도우에서 완전히 제거되면 종류 수 감소
                }
                
                left++; // 윈도우 왼쪽 포인터 이동
            }

            // 현재 윈도우의 길이 (과일 수)로 최대값 갱신
            max = Math.max(max, right - left);
        }

        return max; // 최대 수확 가능한 과일 수 반환
    }
}

차이점 정리