Lv.1simulationstack
소행성 충돌
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
일직선 위에 소행성들이 왼쪽부터 순서대로 asteroids로 주어집니다. 절댓값은 소행성의 크기, 부호는 방향입니다. 양수는 오른쪽으로, 음수는 왼쪽으로 움직이며 모든 소행성의 속도는 같습니다.
오른쪽으로 가는 소행성과 왼쪽으로 가는 소행성이 마주치면 충돌합니다.
- 크기가 작은 쪽이 부서집니다.
- 크기가 같으면 둘 다 부서집니다.
- 같은 방향으로 움직이는 소행성끼리는 절대 만나지 않습니다.
모든 충돌이 끝난 뒤 남은 소행성들을 왼쪽부터 순서대로 배열에 담아 반환하세요. 남은 소행성이 없으면 빈 배열입니다.
입출력 예
| asteroids | result |
|---|---|
[5, 10, -5] | [5, 10] |
[8, -8] | [] |
[10, 2, -5] | [10] |
입출력 예 설명
예 1 — 10과 -5가 충돌해 -5가 부서집니다. 5와 10은 같은 방향이라 만나지 않습니다.
예 2 — 크기가 같아 둘 다 부서집니다.
예 3 — -5가 먼저 2를 부수고, 이어서 10과 부딪혀 부서집니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(asteroids: int[]) → int[]
제한 사항
-
asteroids.length -
asteroids[i],asteroids[i]
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| asteroids | 기대 출력 |
|---|---|
[5,10,-5] | [5,10] |
[8,-8] | [] |
[10,2,-5] | [10] |
힌트
힌트
왼쪽부터 소행성을 하나씩 보면서 "지금까지 살아남은 소행성"을 스택에 쌓아 보세요.
- 오른쪽으로 가는 소행성은 일단 스택에 넣습니다.
- 왼쪽으로 가는 소행성이 오면, 스택 맨 위가 오른쪽으로 가는 소행성인 동안 둘을 충돌시킵니다. 스택 쪽이 작으면 꺼내고 계속, 같으면 둘 다 없애고 멈춤, 크면 들어온 소행성만 부서집니다.
- 살아남은 왼쪽 소행성은 더 부딪힐 상대가 없으므로 스택에 넣습니다.
각 소행성은 스택에 한 번 들어가고 한 번 나오므로 입니다.
복잡도 목표
충돌하는 쌍을 매번 처음부터 찾아 배열 중간에서 지우면 이 되어 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1368 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 3 | 판정만 |