23.03.02. 풀었던 문제들

Leetcode 443. String Compressiong

 어디선가 많이 본 string 압축 문제이다. 추가 공간을 할당하고 indexing 실수만 없다면 쉽게 문제를 해결할 수 있지만 이 문제는 in-place 방식으로 풀어야 한다는 추가 제약사항이 있다.

 문제는 주어진 대로 구현하면 된다. 어떤 시점 i부터 chars[i]와 같은 마지막 index인 end를 저장하고, i부터 end까지 length를 계산해 넣어주면 된다.

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size(), cur = 0;
        for(int i = 0; i<n;){
            int end = i; // end : chars[i]와 같은 마지막 index
            while(end + 1< n && chars[i] == chars[end + 1]){
                end++;
            }
            
            // get compressed string
            string str = ""; str += chars[i];
            if(i != end){
                str += to_string(end - i + 1);
            }
            i = end + 1;

            // replace
            for(char c : str){
                chars[cur] = c;
                cur++;
            }
        }
        chars.erase(chars.begin() + cur, chars.end());
        return chars.size();
    }
};

 

시간복잡도

 앞에서부터 훑고 가기 때문에 O(n)이다.

 

공간복잡도

 숫자를 저장하기 위해 str이라는 변수를 사용했다. input이 최대 2000이므로 4만큼의 크기를 사용하며, O(1)이다.