RLE(Run-Length Encoding, 런 길이 인코딩)는 연속적으로 반복되는 값을 압축하여 표현하는 기법입니다. 이번 글에서는 런 길이 인코딩된 시퀀스를 순회할 수 있는 반복자를 C++로 구현하는 방법을 단계별로 살펴보겠습니다.
문제 정의
반복자는 RLEIterator(int[] A) 생성자를 호출하여 초기화합니다. 여기서 A는 어떤 시퀀스의 런 길이 인코딩 결과입니다. 즉, 모든 짝수 인덱스 i에 대해 A[i]는 비음수 정수 A[i+1]이 시퀀스에서 반복되는 횟수를 의미합니다.
이 반복자는 다음 함수를 지원합니다.
next(int n): 다음 n개의 요소(n >= 1)를 소진(exhaust)하고, 그중 마지막에 소진된 요소를 반환합니다. 만약 소진할 요소가 남아 있지 않다면 대신 -1을 반환합니다.
동작 예시
A = [3,8,0,9,2,5]는 시퀀스 [8,8,8,5,5]의 런 길이 인코딩입니다. 이 시퀀스는 "여덟이 세 개, 아홉은 없음, 다섯이 두 개"로 읽을 수 있습니다.
A로 반복자를 초기화한 후 next(2), next(1), next(1), next(2)를 차례로 호출하면 최종 결과는 [8, 8, 5, -1]이 됩니다.
풀이 접근 방식
이 문제는 포인터를 활용한 직관적인 순회 방식으로 해결할 수 있습니다.
초기화자에서 배열을 A로 저장하고, 현재 위치를 가리키는 index를 0으로 설정합니다.
next() 메서드는 n을 입력받아 다음과 같이 동작합니다.
index가 배열 크기보다 작고 n이 A[index]보다 큰 동안, n에서 A[index]만큼 빼고 index를 2씩 증가시켜 다음 쌍으로 이동합니다.
순회 후 index가 배열 크기 이상이라면 더 이상 소진할 요소가 없으므로 -1을 반환합니다.
그렇지 않으면 A[index]에서 n을 차감하여 남은 개수를 갱신합니다.
마지막으로 A[index + 1], 즉 해당 런의 실제 값을 반환합니다.
C++ 구현 코드
#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;
}입력
[3,8,0,9,2,5]로 초기화한 후 next(2), next(1), next(1), next(2) 호출
출력
8 8 5 -1
복잡도 분석
next() 메서드는 호출될 때마다 이미 소진된 런을 건너뛰므로, 전체 실행 과정에서 index는 최대 배열 길이까지만 이동합니다. 따라서 m번의 next 호출에 대한 총 시간 복잡도는 O(m + k)(k는 인코딩 배열의 길이)이며, 공간 복잡도는 O(k)입니다.