23.04.11. 풀었던 문제들

Leetcode 2390. Removing Stars From a String

 문제를 보면 stack을 쓰는 쉬운 문제라는 것을 깨달을 수 있다. 어제 풀었던 문제와도 같은 문제. 그러나 stack을 쓰면 O(n)만큼 쓰고, 또 그걸 string에 넣어야 하니까 O(2n)이 된다. 그래서 그냥 바로 string을 쓰면 된다. string에 push_back(또는 + 연산), pop_back 연산이 있기 때문이다.

// Runtime 68 ms Beats 95.74%
// Memory 25.9 MB Beats 57.75%
 
class Solution {
public:
    string removeStars(string s) {
        string answer = "";
        for(char c : s){
            if(c == '*'){
                answer.pop_back();
            }
            else{
                answer += c;
            }
        }
        return answer;
    }
};

 

시간복잡도

 s를 처음부터 끝까지 순회하므로 O(n). string에 push_back()이나 pop_back()하는 것은 O(1)이 걸린다. 따라서 O(n)

 

공간복잡도

 O(n) size의 answer string을 사용한다.