Leetcode 735. Asteroid Collision

https://leetcode.com/problems/asteroid-collision/description/

Asteroid Collision - LeetCode

문제

소행성의 정보를 정수로 담고 있는 asteroids 배열이 주어진다. 배열에 담겨 있는 각 소행성의 절대값은 소행성의 크기를 나타내며 부호는 소행성이 날아가고 있는 방향을 의미한다(음수는 왼쪽, 양수는 오른쪽) 각 소행성은 똑같은 속도로 움직이고 있다.

 

위의 정보를 바탕으로 소행성이 모두 충돌하고 난 후의 상태를 찾는 것이 목표이다. 충돌의 경우 절대값이 낮은 소행성이 부숴진다. 만약 같은 사이즈의 소행성이 충돌하는 경우는 모두 파괴되는 것으로 한다. 같은 방향으로 움직이는 소행성은 절대 만나지 않는다.

 

코드

class Solution:

    def asteroidCollision(self, asteroids: List[int]) -> List[int]:

        alive = []

        asteroids = asteroids[::-1]

        s = []

        while asteroids:

            asteroid = asteroids.pop()

            if asteroid < 0 and not s:

                alive += [asteroid]

            elif asteroid < 0 and s:

                # 1 1, asteroid == -1

                while s:

                    if abs(asteroid) > s[-1]:

                        s.pop()

                        if not s:

                            alive += [asteroid]

                    elif abs(asteroid) == s[-1]:

                        s.pop()

                        break

                    else:

                        break

            elif asteroid > 0:

                s += [asteroid]

                   

        alive += s

               

        return alive

---

스택을 이용한다면 금방 풀수 있는 문제!