파이썬으로 로켓 충돌 후 최종 상태를 찾는 프로그램

문제 개요

숫자로 이루어진 리스트 nums가 주어집니다. 각 숫자는 로켓의 크기와 방향을 동시에 나타내며, 양수는 오른쪽으로 이동하는 로켓을, 음수는 왼쪽으로 이동하는 로켓을 의미합니다. 숫자의 절댓값은 로켓의 크기를 뜻합니다.

두 로켓이 충돌할 때 적용되는 규칙은 다음과 같습니다.

• 크기가 다른 두 로켓이 충돌하면 작은 로켓은 파괴되고, 큰 로켓은 그대로 여행을 계속합니다.
• 크기가 같은 두 로켓이 충돌하면 둘 다 파괴됩니다.
• 같은 방향으로 이동하는 로켓끼리는 절대 충돌하지 않습니다(속도가 모두 같다고 가정).

목표는 모든 충돌이 끝난 후 남아 있는 로켓들의 상태를 구하는 것입니다.

예를 들어 입력이 nums = [3, 8, 5, -5]라면 출력은 [3, 8]입니다. 5와 -5가 서로 충돌해 함께 파괴되고, 나머지 로켓들은 살아남기 때문입니다.

접근 방법

이 문제는 스택(Stack)을 활용한 시뮬레이션으로 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

1. 새 리스트 ls를 만들고 첫 번째 원소 nums[0]을 넣습니다.
2. 인덱스 1부터 마지막 원소까지 반복합니다.
   • nums[i] >= 0(오른쪽 이동)이면 그대로 ls의 끝에 추가합니다.
   • 음수(왼쪽 이동)라면 일단 ls의 끝에 추가한 뒤, 앞쪽의 양수 로켓들과의 충돌 여부를 검사합니다.
     • 마지막 원소의 절댓값이 ls[j]보다 크면 ls[j]를 삭제하고 계속 검사합니다.
     • 절댓값이 서로 같으면 두 로켓을 모두 삭제하고 반복을 종료합니다.
     • 절댓값이 더 작으면 마지막 원소(음수 로켓)를 삭제하고 반복을 종료합니다.
3. 모든 처리가 끝나면 ls를 반환합니다.

구현 예제

class Solution:
   def solve(self, nums):
      ls = [nums[0]]
      for i in range(1, len(nums)):
         if nums[i] >= 0:
            ls.append(nums[i])
         else:
            ls.append(nums[i])
            j = len(ls) - 2
            while j >= 0 and ls[j] >= 0:
               if abs(ls[-1]) > ls[j]:
                  ls.pop(j)
               elif abs(ls[-1]) == ls[j]:
                  ls.pop(j)
                  ls.pop(-1)
                  break
               else:
                  ls.pop(-1)
                  break
               j -= 1
      return ls

ob = Solution()
nums = [3, 8, 5, -5]
print(ob.solve(nums))

입력

[3, 8, 5, -5]

출력

[3, 8]

복잡도 분석 및 정리

각 로켓은 리스트에 최대 한 번 추가되고 최대 한 번 제거되므로, 이 풀이의 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 결과를 저장하기 위한 리스트 때문에 최악의 경우 O(n)입니다.

핵심 아이디어는 음수 로켓이 등장했을 때만 충돌 검사를 수행하는 것입니다. 오른쪽으로 이동하는 로켓끼리는 절대 충돌하지 않으므로, 왼쪽으로 이동하는 로켓이 기존의 오른쪽 이동 로켓들과 마주치는 지점만 시뮬레이션하면 전체 충돌 과정을 정확히 재현할 수 있습니다.