decompress run length encoded list

https://leetcode.com/problems/decompress-run-length-encoded-list

불러오는 중입니다...

 

입력으로 들어오는 배열은 페어의 의미로 바라본다. 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.

 

나왔나 48 ms에서 40 ms 줄었다... 음 뭔가 그렇네..