Asteroid Collision
소행성들이 한 줄을 따라 모두 같은 속도로 이동합니다. asteroids의 각 값은 소행성 하나를 나타냅니다. 절댓값은 크기이고 부호는 방향을 나타내며, 양수는 오른쪽, 음수는 왼쪽입니다.
오른쪽으로 이동하는 소행성이 왼쪽으로 이동하는 소행성과 만나면 충돌합니다. 더 작은 소행성은 폭발하고, 크기가 같으면 둘 다 폭발합니다. 같은 방향으로 이동하는 소행성들은 절대 만나지 않습니다. 모든 충돌이 끝난 뒤 남은 소행성들을 원래 순서대로 반환하세요. 결과는 비어 있을 수도 있습니다.
함수
- asteroidsinteger-array
- 왼쪽에서 오른쪽 순서의 소행성, 방향을 나타내는 부호, 크기를 나타내는 절댓값
- 반환값integer-array
- 왼쪽에서 오른쪽으로 남아 있는 소행성들(없을 수도 있음)
제약 조건
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
예제
- 입력
- asteroids = [4, 9, -6, 2, -3]
- 출력
- [4, 9]
- 설명
- 9는 -6과 만나 이깁니다. 2는 -3과 만나 폭발하고, 그다음 -3은 계속 날아가 9와 만나 역시 폭발합니다. 다른 어떤 것도 다른 무언가를 향해 움직이지 않으므로 4와 9가 남습니다.
- 입력
- asteroids = [6, -6]
- 출력
- []
- 설명
- 6과 -6은 크기가 같아서 둘 다 폭발하고 결과는 비어 있습니다.
- 입력
- asteroids = [-2, -7, 3, 8]
- 출력
- [-2, -7, 3, 8]
- 설명
- -2와 -7은 왼쪽으로 날아가고 3과 8은 오른쪽으로 날아가므로, 두 그룹은 서로 멀어집니다. 충돌은 일어나지 않으며 네 개의 소행성은 모두 살아남습니다.
후속 질문
스택은 어떤 소행성이 살아남는지 알려줍니다. 폭발하는 각 소행성에 대해, 그 소행성을 파괴한 소행성의 인덱스도 어떻게 보고할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
충돌하려면 왼쪽에는 오른쪽으로 움직이는 물체가, 오른쪽에는 왼쪽으로 움직이는 물체가 있어야 합니다. 왼쪽으로 움직이는 소행성 앞에 오른쪽으로 움직이는 것이 아무것도 없으면 영원히 안전합니다. 행을 왼쪽에서 오른쪽으로 따라가며 살펴보세요. 새로 나타난 왼쪽 이동 소행성은 앞서 나온 소행성 중 어느 것과 여전히 충돌할 수 있을까요?
새로운 왼쪽 이동체는 가장 가까이 남아 있는 오른쪽 이동체를 먼저 충돌한 다음, 그다음 이동체와 충돌하는 식으로, 폭발하거나 오른쪽 이동체가 모두 사라질 때까지 계속합니다. 지금까지 살아남은 이동체들은 스택처럼 동작합니다. 다음에는 가장 최근에 들어온 이동체만 충돌할 수 있습니다.
생존자들을 스택에 유지하세요. 오른쪽으로 움직이는 것은 모두 푸시하세요. 왼쪽으로 움직이는 것이 나오면 스택 맨 위에 더 작은 오른쪽 이동자가 있는 동안 이를 팝하세요. 맨 위에 같은 크기의 오른쪽 이동자가 있으면 이를 팝하고 새 항목은 버리세요. 맨 위 항목이 더 크면 새 항목을 버리세요. 그렇지 않으면 푸시하세요.
풀이
왼쪽으로 움직이는 소행성 하나가 오른쪽으로 움직이는 소행성들이 길게 이어진 줄을 파괴할 수 있으며, 충돌할 때마다 다음에 충돌할 새로운 한 쌍이 드러날 수 있습니다. 새로운 소행성은 항상 가장 최근에 살아남은 소행성과 먼저 마주치므로, 생존한 소행성들을 스택에 쌓으면 한 번의 순회로 모든 충돌을 처리할 수 있습니다.
한 번에 하나의 충돌 해결하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
오른쪽으로 움직이는 소행성이 왼쪽으로 움직이는 소행성 바로 왼쪽에 있을 때 두 소행성이 충돌한다. 처음으로 그런 쌍을 찾아 충돌을 처리한 다음, 왼쪽부터 다시 훑어보자. 그런 쌍이 더 이상 없으면 앞으로 충돌할 일은 없으며, 현재 행이 답이다.
충돌을 처리하는 순서는 중요하지 않다. 서로 마주 보는 인접한 소행성 두 개는 다른 어떤 소행성과 만나기 전에 서로 만난다.
충돌이 일어날 때마다 행을 새로 훑고 가운데에서 원소를 하나 제거해야 한다. 작은 오른쪽 이동 소행성 9,999개 뒤에 -1000이 있으면, 한 번 훑을 때마다 행을 따라가며 오른쪽 이동 소행성 하나를 없앤다. 약 5 × 10^7번의 단계가 필요하다.
알고리즘
- 소행성을 제거할 수 있도록 행을 복사합니다.
- 왼쪽부터 탐색하여
row[i] > 0이고row[i+1] < 0인 첫 번째 인덱스i를 찾습니다. - 그런 인덱스가 없으면 행을 반환합니다.
- 그렇지 않으면 두 소행성 중 크기가 더 작은 것을 제거하거나, 크기가 같으면 둘 다 제거한 다음 다시 탐색합니다.
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]생존자 스택
핵심 아이디어
지금까지 살아남은 운석을 스택에 보관합니다. 스택에는 오른쪽으로 움직이는 운석 다음에 왼쪽으로 움직이는 운석이 오는 경우가 없습니다. 그런 쌍은 이미 충돌했을 것이므로, 스택에는 충돌에서 벗어난 왼쪽 이동 운석들이 오른쪽 이동 운석들 앞에 놓입니다.
새로운 오른쪽 이동 운석은 스택의 모든 운석을 피해 날아가므로 스택에 넣습니다. 새로운 왼쪽 이동 운석은 맨 위에 있는 오른쪽 이동 운석들을 향해 날아가며 가장 최근 운석과 먼저 만납니다. 따라서 맨 위 운석만 다음에 충돌할 수 있는 운석입니다. 첫 번째 예시에서는 -3이 2를 꺼낸 다음 9와 충돌해 폭발하고, 원래 순서대로 된 스택 [4, 9]가 정답입니다.
각 운석은 최대 한 번 스택에 들어가고 최대 한 번 꺼내지므로, 왼쪽 이동 운석 하나가 긴 연속 구간을 없애더라도 이 순회는 O(n)입니다.
알고리즘
- 남은 운석의 빈 스택으로 시작합니다.
- 각 운석에 대해 오른쪽으로 이동하면 스택에 넣고 계속합니다.
- 왼쪽으로 이동하면, 맨 위에서부터 자신보다 작은 오른쪽 이동 운석을 꺼냅니다.
- 이제 맨 위에 같은 크기의 오른쪽 이동 운석이 있으면 꺼내고 새 운석을 버립니다. 맨 위에 더 큰 오른쪽 이동 운석이 있으면 새 운석을 버립니다. 그렇지 않으면 새 운석을 스택에 넣습니다.
- 스택을 아래에서 위 순서로 반환합니다.
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
함정과 경계 사례
- 왼쪽으로 움직이는 물체 뒤에 오른쪽으로 움직이는 물체가 오는 경우를 충돌로 처리하는 것.
[-2, -7, 3, 8]에서는 두 그룹이 서로 멀어지며 네 개 모두 살아남습니다. - pop에
while대신if를 사용하는 것.[1, 2, 3, 4, 5, -15]에서는 왼쪽으로 움직이는 물체가 오른쪽으로 움직이는 물체 다섯 개를 모두 파괴하고 살아남습니다. - 크기가 같은 경우를 놓치는 것.
[6, -6]에서는 6을 pop하고 -6을 버려야 하며, 결과는 빈 배열이어야 합니다. - 패배한 왼쪽으로 움직이는 물체를 push하는 것.
[9, -6]에서는 -6이 폭발하므로 스택에 들어가면 안 됩니다. 아직 살아 있는지 여부를 나타내는 플래그를 유지하세요.
자주 묻는 질문3
Asteroid Collision의 시간 복잡도는 얼마인가요?
생존 천체를 스택에 저장하면 모든 소행성은 최대 한 번씩만 푸시되고 팝되므로 시간 복잡도는 O(n)이고 공간 복잡도는 O(n)입니다. 충돌할 때마다 행을 다시 스캔하면 O(n²)의 비용이 듭니다.
Asteroid Collision에 스택이 적합한 자료 구조인 이유는 무엇인가요?
새로운 소행성은 가장 가까운 생존자에게만 도달할 수 있으며, 그들을 가장 최근에 도착한 순서부터 가장 먼저 도착한 순서까지 만납니다. 이것이 후입선출입니다. 마지막에 스택에 남아 있는 것은 더 이상 충돌할 수 없으므로, 그것이 마지막 행입니다.
소행성 충돌 문제를 추가 공간 O(1)로 해결할 수 있을까요?
네, 입력값을 덮어써도 된다면 가능합니다. 배열의 앞부분을 스택으로 사용하세요. 쓰기 인덱스 top을 유지하고, asteroids[top-1]와 비교한 다음 처음 top개 항목을 반환하세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def asteroidCollision(asteroids):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
asteroids = [4, 9, -6, 2, -3]
예상 출력
[4, 9]