입력으로 들어오는 배열은 페어의 의미로 바라본다. RLE 알고리즘에 이해가 필요 한대 어렵지 않다.
2A3B4C 가 있다면 RLE 인코딩을 해제한다면 AABBBCCCC 가 된다.
최초의 코드는 아래와 같다.
class Solution {
public:
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> arr;
for (int i = 0; i < nums.size(); i += 2) {
int cand = nums[i];
int d = nums[i + 1];
for (int j = 0; j < cand; j++) {
arr.push_back(d);
}
}
return arr;
}
};
이런 문구가 보여서 뭔가 좀 더 최적화가 가능한 걸로 보인다. 이유가 무엇? 어떻게 하실?
Runtime: 48 ms, faster than 58.95% of C++ online submissions for Decompress Run-Length Encoded List. Memory Usage: 10.7 MB, less than 100.00% of C++ online submissions for Decompress Run-Length Encoded List.
아무래도 매번 push_back 을 호출하면서 메모리 동적 할당으로 인하여 속도가 늦어진 걸로 파악된다. stl 메서드 중 reserve를 통하여 미리 메모리를 확보해 놓고 재 검사하였다.
class Solution {
public:
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> arr;
arr.reserve(100);
for (int i = 0; i < nums.size(); i += 2) {
int cand = nums[i];
for (int j = 0; j < cand; j++) {
arr.push_back(nums[i + 1]);
}
}
return arr;
}
};
결과는
Runtime: 40 ms, faster than 98.93% of C++ online submissions for Decompress Run-Length Encoded List. Memory Usage: 10.6 MB, less than 100.00% of C++ online submissions for Decompress Run-Length Encoded List.
