문제 설명
나무들이 한 줄로 늘어서 있고, i번째 나무는 tree[i]라는 종류의 과일을 생산한다고 가정해 봅시다. 우리는 원하는 나무 아무 곳에서나 시작해 다음 단계를 반복해서 수행할 수 있습니다.
- 현재 나무에서 과일 하나를 바구니에 담습니다. 더 이상 담을 수 없으면 중단합니다.
- 오른쪽에 있는 다음 나무로 이동합니다. 오른쪽에 나무가 더 없으면 중단합니다.
바구니는 총 두 개이며, 각 바구니에는 어떤 종류의 과일이든 원하는 만큼 담을 수 있습니다. 단, 각 바구니에는 한 가지 종류의 과일만 담아야 한다는 제약이 있습니다. 목표는 이 규칙 안에서 수집할 수 있는 과일의 최대 개수를 구하는 것입니다.
예를 들어 나무 배열이 [0, 1, 2, 2]라고 하면 정답은 3입니다. 두 번째 나무부터 시작해 [1, 2, 2]를 모두 수집할 수 있기 때문입니다. 반면 첫 번째 나무에서 시작하면 [0, 1]까지만 수집할 수 있습니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 맵(해시맵)을 조합하면 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 왼쪽 포인터 j와 오른쪽 포인터 i로 탐색 구간을 유지합니다.
- 맵 m에는 현재 구간에 포함된 과일 종류별 개수를 저장합니다.
- 새 과일을 추가했을 때 서로 다른 종류가 3개 이상이 되면, 왼쪽 끝부터 과일을 제거해 종류가 2개 이하가 될 때까지 창을 축소합니다.
- 매 단계마다 현재 구간 길이(i - j + 1)로 최댓값을 갱신합니다.
알고리즘 단계
- n := tree의 크기, j := 0, ans := 0으로 초기화합니다.
- 맵 m을 생성합니다.
- i를 0부터 n-1까지 순회합니다.
- m[tree[i]]를 1 증가시킵니다.
- m의 크기가 2보다 크고 j <= i인 동안 다음을 반복합니다.
- m[tree[j]]를 1 감소시킵니다.
- m[tree[j]] == 0이면 m에서 tree[j]를 삭제합니다.
- j를 1 증가시킵니다.
- ans := max(i - j + 1, ans)로 갱신합니다.
- ans를 반환합니다.
이 방식은 각 요소가 최대 두 번(추가와 제거) 처리되므로 전체 시간 복잡도는 O(n)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int totalFruit(vector<int>& tree) {
int n = tree.size();
int j = 0;
map <int, int> m;
int ans = 0;
for(int i = 0; i < n; i++){
m[tree[i]] += 1;
while(m.size() > 2 && j <= i){
m[tree[j]]--;
if(m[tree[j]] == 0)m.erase(tree[j]);
j++;
}
ans = max(i - j + 1, ans);
}
return ans;
}
};
main(){
vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
Solution ob;
cout <<(ob.totalFruit(v));
}
실행 결과
입력
[3,3,3,1,2,1,1,2,3,3,4]
출력
5
위 예제에서 가장 긴 유효한 구간은 [1, 2, 1, 1, 2]로, 그 길이가 5입니다. 따라서 프로그램은 5를 출력합니다.