리트코드 735. Asteroid Collision

https://leetcode.com/problems/asteroid-collision/description/?envType=study-plan-v2&envId=leetcode-75

LeetCode - The World's Leading Online Programming Learning Platform

소행성을 나타내는 정수로 이루어진 소행성 배열이 주어진다.
각 소행성에서 절대값은 크기를 나타내고 부호는 방향을 나타낸다(양수는 오른쪽, 음수는 왼쪽). 각 소행성은 같은 속도로 움직인다.
모든 충돌 후 소행성들의 상태를 반환한다.

두 소행성이 만나면 더 작은 소행성이 폭발한다. 둘의 크기가 같으면 둘 다 폭발한다. 같은 방향으로 움직이는 두 소행성은 절대 만나지 않는다.

접근

1. 살아남은 소행성들을 보관하는 스택을 생성한다.
2. 소행성들을 순회하면서 스택의 소행성들과 비교한다.
   1. 만약 스택이 비어있거나, 소행성이 오른쪽으로 갈 경우(양수인 경우) 스택의 소행성과 절대 부딪히지 않으므로, 스택에 추가한다.
   2. 그렇지 않을 경우 while문을 진행하면서 다음과 같은 조건을 확인한다.
      1. 스택이 비어있거나 스택의 소행성이 왼쪽으로 갈 경우 (새로운 소행성이 오른쪽으로 오기 때문에 절대 부딪히지 않으므로 스택에 추가한다. -> break
      2. 스택의 소행성과 절댓값이 동일할 경우에는 두 소행성이 폭발하므로 스택의 마지막 소행성을 제거한다. -> break
      3. 만약 스택의 소행성이 더 클 경우에는 다음 소행성을 순회한다. -> break
      4. 모든 조건문에 해당되지 않을 경우에는 스택의 소행성이 순회하는 소행성보다 작다는 것을 의미하므로, 스택의 소행성을 제거하고 while문을 다시 타도록 한다.

풀이

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stk = []
        for ast in asteroids: # O(n)
            if not stk or ast > 0: # O(1)
                stk.append(ast) # O(1)
            else: 
                while True: # Worst case O(n)
                    if not stk or stk[-1] < 0: # O(1)
                        stk.append(ast) # O(1)
                        break
                    elif stk[-1] == -ast: # O(1)
                        stk.pop() # O(1)
                        break
                    elif stk[-1] > -ast: # O(1)
                        break
                    else:
                        stk.pop() # O(1)
        return stk

 

시간복잡도 : 전반적인 시간복잡도는 O(n)이다. 중첩되는 while문의 경우 최악의 경우 시간복잡도가 O(n)이 될 수 있지만, for 문을 통해 순회되는 소행성(ast)들은 한 번씩만 스택에 들어가고 나가게 되기 때문이다.

 

공간 복잡도 : 살아남은 소행성들을 관리하기 위한 스택 배열을 생성하기 때문이 공간복잡도는 O(n)이 발생한다.