[leetcode] 904. Fruit into Baskets

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

---

슬라이딩 윈도우 문제.
인덱스를 가리키는 변수 l(왼쪽), r(오른쪽)을 둔다.
tree[l]을 포함하여 수집할 수 있는 최대 범위를 r로 구한다.
tree[l ~ r]이 과일종류가 3개 이상이 되기전까지 r을 증가시킨다. 
r을 구했으면 tree[l]을 포함할 때 수집할 수 있는 최대 과일 수를 구할 수 있다. (l~r 범위)

ex) 

l = 0. r = 4 -> r - l + 1 = 5(0번째 인덱스를 포함하여 수집할 수 있는 최대 과일 수)
다음 탐색 시 tree 배열을 다시 탐색하지 않으려면 구한 범위에서 tree[l]이 아닌 과일의 종류가 무엇인지 알아야하고 이 과일이 가장 나중에 나타난 인덱스를 알아야한다.

 

ex)

l이 오른쪽으로 한 칸 움직였을 때 another 수는 1임을 저장했으므로 배열의 재탐색없이 알아낼 수 있다.
그리고 another이 가장 마지막에 등장한 인덱스를 저장해둠으로써 l과 비교해서 우리가 원하는 배열 인덱스 안에 위치하는지 알 수 있다.

위 그림처럼 l이 4인덱스 까지 움직였을 때, another이 여전히 1이고 가장 마지막 나타난 인덱스가 3이라면(사실 위 예제대로라면 1인덱스가 갱신되서 3이아닌 6이지만 3이라 가정하고 이야기한다.) 3은 l인덱스인 4보다 작아지므로 더이상 another이 될 수 없다. (우리가 바라는 범위는 l보다 큰 인덱스다.)
따라서 이경우는 l 이상의 인덱스 중 2가 아닌 다른 수를 another로 갱신해줘야 한다. -> 인덱스가 5인 1이 another 과일이 될 것이다.

위와 같이 now가 1이고 another이 4인 경우 tree[l+1]이 another인 경우가 있다.
이 경우 now가 다음 another이 될 수 있는지 체크해야 한다.
now가 나타난 마지막 인덱스는 6이다. 이는 l+1인 3보다 크므로 우리가 탐색하고자 하는 범위내에 속한다.

따라서 now는 다음에 탐색하고자 하는 범위에서도 유효한 값이므로  another값을 now(1)로 갱신해준다. another값이 다음에 탐색하고자 하는 범위에서 유효하지 않은 값이면 (마지막으로 나타난 인덱스가 l+1 보다 작은경우) another은 빈 값으로 갱신한다.

시간 복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/904.%20Fruit%20Into%20Baskets.cpp