실행 길이로 인코딩된 시퀀스를 반복하는 반복자를 생성해야 한다고 가정합니다. 여기서 반복자는 RLEIterator(int[] A)를 호출하여 초기화됩니다. 여기서 A는 시퀀스의 실행 길이 인코딩입니다. 따라서 모든 짝수 i에 대해 A[i]는 음이 아닌 정수 값 A[i+1]이 시퀀스에서 반복되는 횟수를 알려줍니다. 여기서 iterator는 하나의 기능을 지원합니다 -
-
next(int n):이 함수는 다음 n개 요소(n>=1)를 소진하고 이러한 방식으로 소진된 마지막 요소를 반환합니다. 따라서 소진할 요소가 남아 있지 않으면 next는 대신 -1을 반환합니다.
시퀀스 [8,8,8,5,5]의 실행 길이 인코딩인 A =[3,8,0,9,2,5]로 시작한다고 가정합니다. 이것은 시퀀스가 "3개의 8, 0의 9, 2개의 5"로 읽을 수 있기 때문에 수행됩니다. 따라서 A로 초기화한 후 next(2), next(1), next(1), next(2)를 호출하면 최종 결과는 [8, 8, 5, -1]이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이니셜라이저에서 배열을 A로 초기화하고 index :=0
으로 설정합니다. -
next() 메서드에서는 n을 입력으로 받습니다. 이것은 다음과 같이 작동합니다
-
동안 인덱스 A[인덱스]
-
n :=n – A[인덱스], 인덱스 2 증가
-
-
인덱스> 배열 A의 크기인 경우 -1을 반환
-
A[인덱스] :=A[인덱스] – n
-
반환 A[인덱스 + 1]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class RLEIterator {
public:
vector <int> A;
int idx = 0;
RLEIterator(vector<int>& A) {
this->A = A;
idx = 0;
}
int next(int n) {
while(idx < A.size() && n > A[idx]){
n -= A[idx];
idx += 2;
}
if(idx >= A.size()) return -1;
A[idx] = A[idx] - n;
return A[idx + 1];
}
};
main(){
vector<int> v = {3,8,0,9,2,5};
RLEIterator ob(v);
cout << (ob.next(2)) << endl;
cout << (ob.next(1)) << endl;
cout << (ob.next(1)) << endl;
cout << (ob.next(2)) << endl;
} 입력
Initialize with [3,8,0,9,2,5] and call next(2), next(1), next(1), next(2)
출력
8 8 5 -1