99클럽 코테 스터디 36일차 TIL Removing Stars From a String

https://leetcode.com/problems/removing-stars-from-a-string/submissions/1298687817/

 

 

 

1. 문제 및 접근

 

 

 

 

2390. Removing Stars From a String

String이 주어지면 그 안에 있는 *가 들어온 만큼 왼쪽 char를 지우기

순서가 중요하다 * 나오면 바로 왼쪽 꺼 지워주기

전부 다 유효하다.

 

Input: s = "leet**cod*e"

Output: "lecoe"

 

왼쪽이니까 stack에 넣으면서 *이 나오면 다음 인덱스로 가면 될 듯

 

 

 

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.

 

 

 

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters and stars *.
• The operation above can be performed on s.

 

 

 

 

 

 

 

 

2. 잘못 풀이

 

while (!stack.isEmpty()) { // isEmpty ?

    int star = 0;

    if(stack.peek() == '*') {


    while (stack.peek() == '*') {
        char n = stack.pop();
        star++;

        }
    for (int i = 0; i < star; i++) {
        stack.pop();

    }}

    else deque.addFirst(stack.pop());




}

 

 

*이 들어오면 들어온만큼 횟수를 세어주고, 뒤에서부터 지워도 되는 줄 알고

 

stack에서 *을 만나면, *이 이어지는 횟수동안 세고 뒤에서부터 지워줬다.

 

 

 

 

ex) s =  [abb*cdfg*****x*]

 

 

 

1. [abb*cdfg*****x*]

• stack의 첫 * 하나에 대응하는 x를 뒤에서 부터 지움   
• [abb*cdfg*****x*]  ->   [abb*cdfg*****]

 

 

 

2. [abb*cdfg*****]

• 뒤에서 센 *이 5개니까 대응하는 [b*cdfg]를 지움       
• [abb*cdfg*****]   ->   [abb]

 

 

 

result = [abb]     (틀린 답이다)

 

 

 

 

 

 

 

문제에서 요구하는 것은 *을 앞에서부터 만나자 마자 왼쪽을 지워줘야 한다.

 

 

 

 

 

1. [abb*cdfg*****x*]

• 첫 *에 대응하는 왼쪽 [b]를 지움                         
• [abb*cdfg*****x*]    ->   [abcdfg*****x*]

 

 

2. [abcdfg*****x*]

• 두 번째 * 5개에 대응하는 왼쪽 [bcdfg]를 지움 
• [abcdfg*****x*]        ->    [ax*]

 

 

3. [ax*]

• 세 번째 * 하나에 대응하는 왼쪽 [x]를 지움
• [ax*]  ->  [a]

 

 

result = [a]

 

 

 

 

 

 

 

 

 

3. 풀이

 

public class RemovingStarsFromAString정답 {

    // 2390. Removing Stars From a String
    // String이 주어지면 그 안에 있는 *가 들어온 만큼 왼쪽 char를 지우기
    // 순서가 중요하다 * 나오면 바로 왼쪽 꺼 지워주기
    // 전부 다 유효하다.

    // Input: s = "leet**cod*e"
    //Output: "lecoe"

    //왼쪽이니까 stack에 넣으면서 *이 나오면 다음 인덱스로 가면 될 듯

    // 100000이 들어오고,

    public static void main(String[] args) {
        String s = "abb*cdfg*****x*";
        String s1 = "leet**cod*e";

        RemovingStarsFromAString정답 main = new RemovingStarsFromAString정답();
        System.out.println(main.removeStars(s1));
    }



    public String removeStars(String s) {

        Deque<Character> deque = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int length = s.length();

        for (int i = 0; i < length; i++) {

            char current = s.charAt(i);
            if (current == '*') {

                deque.removeLast();

            } else  deque.add(current);
        }

        while (!deque.isEmpty()) {
            sb.append(deque.removeFirst());

        }

        return sb.toString();


        }
    }

 

 

 

 

 

 

 

 

 

3-1. deque와 StringBuilder

 

 

 

 

 

stack으로 풀어도 되지만, 나중에 StringBuilder에 담기 쉽게 deque로 풀어야 겠다고 생각했다.

 

 

 

 

 

deque에 대한 포스팅은 이미 있으니 pass

 

99클럽 코테 스터디 17일차 TIL 구명보트 feat. deque

99클럽 코테 스터디 17일차 TIL 구명보트 feat. deque

 

 

 

 

 

 

 

 

3-2. s의 요소를 deque에 추가

 

 

 

 

너무 간단하다.

 

 

 

 

현재 char(i)가 " 라면 ?

 

 

deque에서 마지막 요소를 지워준다.

가능한 이유는 문제에서 모든 작업은 가능하게 주어진다고 했기 때문에 따로 없는 요소를 뺄 예외처리 안해도 된다.

 

 

 

 

 

현재 char(i)가 " 아니라면 ?

 

deque에 앞에서 부터 추가

 

 

 

 

 

 

 

 

 

3-3. deque의 요소를 StringBuilder에 추가

 

 

 

 

 

추가 후 String으로 반환하면 끝

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. 마무리

 

 

 

문제를 잘못 읽고 이해했는데, 오늘은 미들러 문제인가 싶을 정도로 너무 쉬웠다.

요새 너무 편하게 하려고 deque에만 손이 가는데.. 의도적으로 다른 자료구조도 계속 써야겠더라

 

아니 근데 leetcode에서 내 코드의 시간 복잡도와 공간 복잡도를 계산해주는 기능이 있더라 ?

엄지 척도 해줌

 

 

짜식 욕만 했는데 진짜 오늘부터 칭찬 +1 해준다.

 

계산이 직관적으로 힘들 때 보고 좀 더 시간이나 공간 복잡도를 줄이는 방법을 보안해봐야겠다

 

이번은 둘 다 O(N)이라 다른 코드를 참조하기 보다 다른 문제를 하나 더 풀어봐야겠네