[리트코드/leetcode/python] 735. Asteroid Collision

이미지를 누르면 문제 링크를 보실 수 있습니다

한 번 문제를 이해해봅시다. 

입력값으로 주어진 asteroids 배열은 소행성 배열입니다. 이 소행성은 양수값을 가질 수도 있고, 음수값을 가질 수도 있습니다.

양수값을 가진 소행성은 오른쪽으로 움직이고, 음수값을 가진 소행성은 왼쪽으로 움직입니다.

모든 소행성은 크기에 관계없이 같은 속도로 움직이기 때문에, 추월, 정지 등의 사건이 발생하지 않습니다.

 

두 소행성이 충돌했을 때는, 소행성의 크기의 절댓값에 따라서 소행성이 사라집니다.

예를 들어, '2'의 소행성과 '-5'의 소행성이 충돌했다면, '-5'의 소행성이 더 절댓값이 크기 때문에 '2'의 소행성이 없어지고, '-5'의 소행성은 계속해서 움직였던 방향대로 지나갑니다.

이 때, 두 소행성의 크기의 절댓값이 같다면, 두 소행성이 충돌했을 때는 두 소행성 모두 없어진다는 특징이 있습니다.

 

먼저, 이 문제를 접했을 때, 흡사 괄호문제처럼 '스택' 알고리즘이 생각났습니다.

소행성 배열을 돌면서 양수의 크기인 소행성을 스택에 넣고, 음수인 소행성이 나온다면, 제일 최근에 스택에 넣었던 양수의 소행성의 절댓값과 현재 마주친 음수의 소행성의 절댓값을 비교하여 어떤 소행성을 소거할지 결정하는 로직입니다.

 

해당 로직으로 알고리즘을 풀었지만, 어딘가 계속 예외 테스트 케이스가 나왔습니다.

소행성 배열을 돌면서 소행성 배열이 변하는 동시성 문제라든지, 스택이 최신화 된다 한들, 해당 스택을 다시 검사해야 하는 등의 번거로움이 생겨났습니다.

 

그래서, 생각을 다시 해봤습니다. 먼저 충돌이 반드시 발생하는 경우가 어떤 경우가 있는지 생각해봤는데요,

소행성 배열을 돌면서 현재 바라보고 있는 소행성이 양수의 소행성이고 바로 그 다음에 오는 소행성이 음수의 소행성일 때만 충돌이 발생하는 것을 깨달았습니다.

예를 들어, [-1,-2,3,5,-2,-2] 라는 소행성 배열이 있다고 하면, 가장 먼저 충돌이 발생하는 곳은 소행성 '5'와 '-2' 사이에서 발생합니다.

(-) 값을 가진 소행성은 계속 왼쪽으로 가고, (+) 값을 가진 소행성은 계속 오른쪽으로 가는 특성 때문입니다.

 

이러한 원리를 가지고 시간복잡도에 생각않고 작성했던 코드는 아래와 같습니다.

class Solution(object):
    def asteroidCollision(self, asteroids):
       
        check = True
        while check :

            check = False

            for i in range(len(asteroids)-1):
                if asteroids[i] > 0 and asteroids[i+1] < 0:
                    check = True
                    if abs(asteroids[i]) < abs(asteroids[i+1]):
                        asteroids.pop(i)
                        
                    elif abs(asteroids[i]) > abs(asteroids[i+1]):
                        asteroids.pop(i+1)
                        
                    else:
                        asteroids.pop(i+1)
                        asteroids.pop(i)

                    break

        return asteroids

하지만, 시간복잡도를 보면, 아주 안좋은 것을 확인할 수 있죠?

비효율적인 코드

속도를 좀 더 개선할 필요가 있었습니다.

매번 pop을 하고 break을 하고 다시 재정비된 asteroids 소행성배열을 확인해야 하는 번거로움 때문에, 저런 비효율이 발생했습니다.

 

check 플래그를 사용하지 않고도 ateroids 를 갱신하면서 답을 찾아는 방법으로 코드를 다시 짜봤습니다.

del 키워드를 사용해서, 특정 원소를 없앴고, asteroids배열을 도는 인덱스 i 를 갱신하면서 조절했습니다.

코드는 아래와 같습니다.

class Solution(object):
    def asteroidCollision(self, asteroids):
    
        i = 0
        while i < (len(asteroids)-1):

            if asteroids[i] > 0 and asteroids[i+1] < 0 and i >=0:
                
                if abs(asteroids[i]) < abs(asteroids[i+1]):
                    del asteroids[i]
                    i-= 1
                
                elif abs(asteroids[i]) > abs(asteroids[i+1]):
                    del asteroids[i+1]
                    i -= 1
            
                else:
                    del asteroids[i]
                    del asteroids[i]
                    i-= 1
            else:
                i += 1

        return asteroids

처음 인덱스부터 asteroids배열을 도는데, asteroids[i] 원소가 양수이고, 바로 그 다음 원소가 음수임과 동시에, 인덱스가 i>=0 이라면, 

소행성 크기의 절댓값 비교를 시작합니다.

각 경우에 따라, 소거되는 소행성을 del 하고, i를 1 빼줌으로써 재정비된 ateroids 를 다시 이 시점부터 체크할 수 있도록 조절해줍니다.

소행성 충돌이 발생되는 경우가 아니라면, 그냥 인덱스 i를 1 증가시키면 됩니다.

모든 작업이 끝났다면, asteroids에 남은 소행성은 더 이상 충돌이 발생하지 않은 소행성 배열만 남게 됩니다.

조금 더 효율적인 코드

이상으로 소행성 배열에서 조건에 맞게 시간복잡도를 줄일 수 있는 735. Asteroid Collision 문제를 정리해봤습니다.