•
문제 설명 : 소행성들이 충돌 시 작은 소행성이 폭발하거나 크기가 같으면 모두 폭발하며, 충돌 후 남은 소행성들을 구하는 문제이다.
•
풀이 방법
◦
제공된 설명이 상당히 아쉬웠다. 문제 이해가 제일 어려웠던거 같다.
◦
처음에는 제공된 배열에서 pop을 하며 진행하려 했지만, 중간에 충돌하지 않는 경우가 섞여있다면 pop 을 통한 작업이 중단되기 때문에 append 를 하면서 배열을 새롭게 만들어주었다.
◦
새롭게 운석이 추가되면 이전 운석까지 모두 확인하기 때문에, N^2라고 시간 복잡도라고 생각할 수 있다.
▪
하지만, 결국 추가 탐색의 경우를 모두 합쳐도 N(제공 배열 길이)번을 넘지 않는다.
▪
따라서, O(N + N) → O(N)이 된다.
•
시간복잡도 :
•
성공 코드
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
result = []
for asteroid in asteroids:
result.append(asteroid)
while len(result) >= 2:
last_asteroid = result[-1]
second_asteroid = result[-2]
# 충돌 가능
if second_asteroid > 0 and last_asteroid < 0:
if abs(second_asteroid) == abs(last_asteroid):
result.pop()
result.pop()
break
elif abs(second_asteroid) > abs(last_asteroid):
result.pop()
break
elif abs(second_asteroid) < abs(last_asteroid):
result[-2] = last_asteroid
result.pop()
else:
break
return result
Python
복사