[LeetCode] Removing Stars From a String

https://leetcode.com/problems/removing-stars-from-a-string/description/?envType=study-plan-v2&envId=leetcode-75

 

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.
 

Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.
 

Constraints:
1 <= s.length <= 105
s consists of lowercase English letters and stars *.
The operation above can be performed on s.

 

---

 

*과 영어 소문자가 섞인 문자열이 주어진다.

*이 있으면 *과 * 왼쪽에 있는 문자 1개를 제거하고, 이를 *이 없을 때까지 반복하고 리턴하는 문제.

*과 *의 왼쪽에 있는 문자열을 지울 수 없는 input은 주어지지 않는다는 전제가 깔려 있다.

 

문제가 심플하고.. 문제를 푸는 것 자체는 오래 걸리지 않았는데 시간 제한 통과를 하지 못했다ㅋㅋㅋ

const removeStars = function(s) {
    // *과 영어 소문자로 이루어진 문자열이 주어진다
    // *이 없을 때까지 *과 *의 왼쪽 영문자 1개를 제거하고 결과를 리턴
    let mustDelete = new Set();
    let textArr = [...s];
    let astarisk = 0;
    textArr.map((char, index)=>{
        if(char == '*'){
            astarisk++;
            let leftOne = index -1;
            mustDelete.add(index);
            // 하나 왼쪽 index를 추가한다
            // 근데 그 다음 글자도 *이라서 그 이전 index가 이미 포함됐다면?
            while(true){
                if(mustDelete.has(leftOne)){
                    leftOne--;
                }else{
                    textArr[leftOne] = "*";
                    mustDelete.add(leftOne);
                    break;
                }
            }
        }
    })
    if(astarisk * 2 == s.length){
        return "";
    }
    s = textArr.join("");
    return s.replaceAll("*", "");
};

 

지워야 하는 문자를 다 *로 바꿔준 다음 replaceAll을 해 주고.. 기타등등.

*이 연달아서 많이 나타나면 while을 정말 많이 돌아야 한다는 단점이 있음ㅋㅋㅋㅋㅋ

그리고 연속적인 *이 나타나면 while문 내에서 이미 해당 *들의 인덱스를 다 저장한 상태인데,

map의 그 다음 순서에서 똑같은 작업을 또 하게 된다.

 

뭔가 우왕좌왕하면서 푸느라 코드가 지저분하고 정리도 덜 돼 있다.

배열로 바꿨다가 다시 string으로 바꿨다가 왔다갔다 난리남ㅠㅠㅋㅋㅋ

나름 * 개수도 카운트해서 * 개수의 2배가 문자열의 길이면 그냥 replace 없이 빈 문자열 리턴하는것도 추가하긴 했지만..

 

아무튼 효율이 안 나오는데.. 너무 어렵게 생각하고 있는 것 같고... 

내 접근 방식이 잘못됐고, 답이 굉장히 짧을 것만 같은 느낌이 자꾸 들었다.

그리고 이번 문제의 주제가 stack이라는 걸 깨닫고... 

 

const removeStars = function(s) {
    const stack = [];
    for(const char of s){
        if(char === "*"){
            stack.pop();
        }else{
            stack.push(char);
        }
    }
    return stack.join("");
}

 

역시나 짧게 해결할 수 있는 문제였음^_^;;

pop은 맨 뒤 엘리먼트를 배열에서 제거하면서 그 엘리먼트를 리턴해 준다. (반대는 shift)

그리고 push는 현재 배열의 맨 뒤에 엘리먼트를 추가해 준다.

한 문자씩 순회하다가 *이 나오면 그냥 pop 해주고 지나가면 *뿐만 아니라 그 앞에 있던 문자까지 제거하는 셈이다.

 

단순하게 생각하는 게 은근 어렵다.