[LeetCode 75/Stack] 2390 - Removing Stars From a String / 735 - Asteroid Collision / 394 - Decode String (Java)

2390 - Removing Stars From a String

---

풀이

*를 만나면 왼쪽에서 가장 가까운 문자 하나 삭제

-> 마지막에 들어온 문자(LIFO) 지움 => 스택

 

• 일반 문자 -> 스택에 push
• * -> 스택에서 pop

---

코드

class Solution {
    public String removeStars(String s) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '*') stack.pop();
            else stack.push(c);
        }

        for (char c : stack) sb.append(c);

        return sb.toString();
    }
}

---

735 - Asteroid Collision

---

풀이

부호: 방향 (양수 - 오른쪽/음수 - 왼쪽)

두 소행성 충돌하면 작은 소행성 폭발/ 크기 같으면 둘 다 폭발/ 같은 방향으로 움직이는 소행성 충돌 X

 

왼쪽에서 오른쪽으로 진행하면서 살아있는 이전 운석 관리

• 충돌 조건: `stack`이 비어 있지 않고, 현재 운석이 왼쪽(-), 스택 top이 오른쪽(+) 
  • top이 더 작음: 스택에서 pop
  • 같은 크기 -> 둘 다 폭발
  • top이 더 큼 -> a만 파괴, 스택 유지
• `destroyed`: 현재 운석이 살아남았는지
  • 충돌에서 살아남았거나 충돌 없었으면 push

else if (c == '[') {
    cntStack.push(k);
    stringStack.push(cur);

    cur = new StringBuilder();
    k = 0;
} else if (c == ']') {
    int repeat = cntStack.pop();
    StringBuilder prev = stringStack.pop();
    for (int i = 0; i < repeat; i++) {
        prev.append(cur);
    }
    cur = prev;
} else cur.append(c);

---

코드

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();

        for (int a : asteroids) {
            boolean destroyed = false;

            while (!stack.isEmpty() && a < 0 && stack.peek() > 0) {
                if (stack.peek() < -a) stack.pop();
                else if (stack.peek() == -a) {
                    stack.pop();
                    destroyed = true;
                    break;
                } else {
                    destroyed = true;
                    break;
                }
            }

            if (!destroyed) stack.push(a);
        }

        int n = stack.size();
        int[] result = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }

        return result;
    }
}

---

394 - Decode String

---

풀이

ex. 3[a2[c]] -> a2[c] = acc -> 3[acc] = accaccacc

=> 중첩 구조로 닫는 괄호 ] 만날 때마다 계산

-> Stack 2개 사용 (숫자 스택: 반복 횟수 저장 / 문자열 스택: 이전까지 문자열 저장)

Stack<Integer> cntStack = new Stack<>();
Stack<StringBuilder> stringStack = new Stack<>();

 

숫자 처리

if (Character.isDigit(c)) {
    k = k * 10 + (c - '0');  
}

 

• '[' 만났을 때
  • 현재 반복 숫자 저장
  • 현재까지 만든 문자열 저장
  • 새로운 내부 문자열 시작
• ']' 만났을 때 -> 이전 상태 복원
  • 현재 문자열 `repeat`(`cntStack.pop()`)만큼 붙여서 이전 문자열 뒤에 연결

else if (c == '[') {
    cntStack.push(k);
    stringStack.push(cur);

    cur = new StringBuilder();
    k = 0;
} else if (c == ']') {
    int repeat = cntStack.pop();
    StringBuilder prev = stringStack.pop();
    for (int i = 0; i < repeat; i++) {
        prev.append(cur);
    }
    cur = prev;
} else cur.append(c);

---

코드

class Solution {
    public String decodeString(String s) {
        Stack<Integer> cntStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        
        StringBuilder cur = new StringBuilder();
        int k = 0;
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');  
            } else if (c == '[') {
                cntStack.push(k);
                stringStack.push(cur);
                
                cur = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                int repeat = cntStack.pop();
                StringBuilder prev = stringStack.pop();
                for (int i = 0; i < repeat; i++) {
                    prev.append(cur);
                }
                cur = prev;
            } else cur.append(c);
        }
        
        return cur.toString();
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode