[leetcode][735] Asteroid Collision

문제 : leetcode.com/problems/asteroid-collision/

---

0이 아닌 정수 값을 가진 asteroids 배열이 주어진다.

요소의 절대값은 크기를 의미하고 부호는 방향을 의미한다. 같은 방향을 가지는 운석들은 부딪히지 않는다.

다른 방향을 가지는 운석들이 만날때 크기가 크거나 같은 운석들이 파괴된다.

asteroids 배열에서 충돌가능한 운석들이 충돌한 뒤 남은 운석들의 배열을 반환하라.

---

[1,2,3,4,-5] 가 주어졌을 때, -5는 4,3,2,1을 차례대로 파괴시킬 수 있고, 만약 [1,2,6,3,-5] 과 같은 운석들이 있다면 -5 운석은 3까지만 파괴시키고 6을 만나 파괴되므로 1,2 운석은 확인하지 않아도 되기 때문에 스택을 사용했다.

배열을 앞에서부터 탐색하면서 스택에 저장한다. 탐색하면서 현재 탐색중인 운석으로 스택에 있는 운석들을 파괴할 수 있는지 판단한다.

스택의 top에 있는 운석과 현재 운석이 같은 방향(부호)을 가지거나 현재 운석이 양수값을 가지면 두 운석은 만날 일이 없으므로 이전 운석들을 파괴시키지 않고 현재 운석을 스택에 저장한다. ex) 스택 top = -3, 현재 운석 = 6 인 경우 두 운석은 만나지 않는다.

두 운석의 방향이 반대고 현재 탐색중인 운석이 음수값이라면 (ex. 스택 top = 3, 현재 운석 = -6. 두 운석은 충돌하고 3 운석이 파괴된다.) 두 운석의 파괴여부를 판단한다.

i) 스택 top 운석 크기 < 현재 운석 크기 : 스택 top 운석이 파괴된다. 파괴되기 때문에 스택을 pop 해주고 다음 top과 현재 운석도 만날 수 있는지, 파괴되는지 다시 판단한다.

ii) 스택 top 운석 크기 > 현재 운석 크기 : 현재 운석이 파괴된다. 현재 운석을 스택에 넣지 않고 다음 운석을 탐색한다. 

iii) 스택 top 운석 크기 = 현재 운석 크기 : 스택 top 운석과 현재 운석이 모두 파괴된다. 스택을 pop 하고 현재 운석도 파괴되기 때문에 별도의 스택 push 없이 다음 운석을 탐색한다.

위 과정을 모든 asteroids 배열을 탐색할 때까지 반복한다.

 

시간복잡도는 O(N). N = asteroids 배열 크기. 엄밀히 말하면 스택에 있는 운석 판단하는데도 시간이 들기 때문에 O(2N)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/735.%20Asteroid%20Collision.cpp