[TIL] 20241114_알고리즘

문제

2390. Removing Stars From a String

You are given a string s, which contains stars *.

In one operation, you can:

Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.

Note:

The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.

정답

class Solution {
  String removeStars(String s) {

    List<String> answer = [];
    for(int i = 0; i < s.length; i++){
        if(s[i] != "*"){
            answer.add(s[i]);
        } else {
            answer.removeLast();
        }
    }
    return answer.join();
  }
}

• 그런데 처음 문제를 풀때 string을 반복문으로 돌면서 substring하는 코드를 제출했더니 시간 초과가 떴다.

class Solution {
  String removeStars(String s) {
    String answer = "";
    for(int i = 0; i < s.length; i++){
        if(s[i] != "*"){
            answer += s[i];
        } else {
            answer = answer.substring(0, answer.length - 1);
        }
    }
    return answer;
  }
}

• 같은 O(N)의 시간복잡도라고 생각했는데, substring 메소드 자체가 O(N)의 시간복잡도를 갖는다고 한다. 생각해보면 문자열을 순환하면서 특정 범위 내의 문자열을 반환하나는 거라 당연한것 같다. 기억하자