LeetCode 2390 - Removing Stars From a String (Medium)

 

💡 문제

LeetCode - 2390번

 

🎯 풀이 과정

별표 (*)를 포함한 문자열 s 에서 다음 규칙에 따라 모든 별표가 제거된 문자열을 반환하는 문제입니다.

별표가 있을 경우 해당 별표보다 앞쪽에 위치한 가장 가까운 문자를 제거합니다.

스택을 활용하면 간단하게 해결이 가능한데, 입력으로 주어지는 문자열의 길이가 크기 때문에 (10^5)

문자열을 순회하며 자료구조에 하나씩 push, pop 하기 보다는 다른 방법을 사용했습니다.

규칙을 활용해서 문자열의 가장 뒤쪽 부터 순회를 해줍니다.

이때 * 를 만나면 answer 에 추가하지 않고 별표의 개수를 계속 세어주다가 일반 알파벳을 발견하면 저장해놨던 별표 개수를 하나씩 줄이고, 만약 저장되어있는 별표 개수가 없다면 그 문자를 answer 에 추가해줍니다.

이렇게 하면 O(n) 의 시간복잡도에 O(1) 의 공간복잡도로 해결 가능합니다.

 

👨‍💻 코드

/**
 * @param {string} s
 * @return {string}
 */
var removeStars = function(s) {
    let answer = ''
    let asterikCount = 0

    for (let i = s.length-1; i >= 0; i -= 1) {
        if (s[i] === '*') {
            asterikCount += 1
        } else {
            if (asterikCount > 0) {
                asterikCount -= 1
            } else {
                answer = s[i]+answer
            }
        }
    }

    return answer
};