문제 설명
1차원 공간상의 소행성 위치를 담고 있는 배열 arr을 입력받아, 모든 충돌이 끝난 후의 최종 상태를 반환하는 JavaScript 함수를 작성해야 합니다.
각 소행성에서 절댓값은 크기를, 부호는 이동 방향을 나타냅니다. 양수는 오른쪽으로, 음수는 왼쪽으로 이동하며, 모든 소행성은 동일한 속도로 움직입니다.
충돌 규칙은 다음과 같습니다.
- 두 소행성이 만나면 크기가 작은 쪽이 폭발합니다.
- 크기가 서로 같으면 두 소행성 모두 폭발합니다.
- 같은 방향으로 이동하는 소행성끼리는 절대 충돌하지 않습니다.
예를 들어 함수에 다음 입력이 주어진다고 가정해 보겠습니다.
입력
const arr = [7, 12, -8];
출력
const output = [7, 12];
출력 설명
12와 -8이 마주쳐 충돌하고, 더 큰 12가 살아남습니다. 7과 12는 모두 오른쪽으로 이동하므로 서로 충돌할 일이 없습니다.
접근 방법: 스택 활용
이 문제는 스택(stack) 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 요소를 하나씩 순회하며 스택에 push합니다.
- 스택의 마지막 두 요소가 충돌 조건(오른쪽으로 이동하는 소행성 뒤에 왼쪽으로 이동하는 소행성)을 만족하는지 확인합니다.
- 충돌 조건이 성립하면 두 소행성의 크기를 비교해 결과를 스택에 반영합니다.
- 더 이상 충돌이 발생하지 않을 때까지 이 과정을 반복합니다.
구현 코드
다음은 위 로직을 구현한 전체 코드입니다.
const arr = [7, 12, -8];
const findState = (arr = []) => {
const track = []
for (const el of arr) {
track.push(el)
while (track[track.length - 1] < 0 && track[track.length - 2] > 0) {
const a = -track.pop()
const b = track.pop()
if (a > b) {
track.push(-a)
} else if (a < b) {
track.push(b)
}
}
}
return track
};
console.log(findState(arr));코드 동작 원리
while 루프의 조건인 track[track.length - 1] < 0 && track[track.length - 2] > 0은 스택 맨 위 두 요소가 각각 왼쪽(-)과 오른쪽(+)으로 이동 중인, 즉 서로 마주 보며 충돌이 임박한 상황을 의미합니다.
충돌이 감지되면 두 값을 꺼내 크기를 비교합니다. 왼쪽으로 이동하는 소행성의 크기가 더 크면 음수 값으로 다시 push하고, 오른쪽으로 이동하는 소행성이 더 크면 양수 값을 그대로 유지합니다. 크기가 같으면 아무것도 push하지 않아 두 소행성이 모두 제거됩니다.
실행 결과
[7, 12]
배열 [7, 12, -8]에서 12와 -8이 충돌해 12만 남고, 7은 그대로 유지되므로 최종 결과는 [7, 12]가 됩니다.