티스토리 뷰
Problem
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
- 2 <= asteroids.length <= 10^4
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Solution
운석의 질량과 움직임 정보가 담긴 배열이 주어질 때 최종 운석 상태를 반환하는 문제입니다.
운석의 질량은 각 원소의 절대값이고, 방향은 음수/양수로 표현합니다.
서로 마주보는 방향일 경우 충돌이 발생해 운석이 큰 쪽만 남게 되고, 질량이 같을 경우 두 운석 모두 소멸합니다.
package io.lcalmsky.leetcode.asteroid_collision;
import java.util.Stack;
public class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int asteroid : asteroids) {
if (asteroid > 0 || stack.isEmpty()) {
stack.push(asteroid);
continue;
}
int abs = Math.abs(asteroid);
while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < abs) {
stack.pop();
}
if (!stack.isEmpty() && stack.peek() == abs) {
stack.pop();
} else if (stack.isEmpty() || stack.peek() < 0) {
stack.push(asteroid);
}
}
int[] result = new int[stack.size()];
for (int i = stack.size() - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return result;
}
}
- asteroids 배열을 순회하면서 각 운석에 대해 다음을 수행합니다:
- 만약 운석의 크기가 양수이거나 스택이 비어있는 경우, 해당 운석을 스택에 추가합니다(stack.push(asteroid)). 이렇게 함으로써, 현재까지 별 대치가 없는 양수 크기의 운석들을 스택에 저장합니다.
- 운석의 크기가 음수인 경우, 운석의 크기를 절대값으로 변경하여 abs 변수에 저장합니다.
- 스택이 비어있지 않고, 스택의 맨 위에 있는 운석이 양수이며 그 크기가 abs보다 작은 경우, 충돌이 발생합니다. 이 경우에는 스택의 맨 위에 있는 운석을 제거합니다(stack.pop()). 이러한 과정을 반복하여 abs보다 작은 양수 크기의 운석들을 스택에서 제거합니다.
- 충돌이 발생했을 때, 스택의 맨 위에 있는 운석의 크기와 abs가 동일하다면 두 운석은 서로 파괴되므로 스택에서 해당 운석을 제거합니다(stack.pop()).
- 충돌이 발생하지 않았거나 스택이 비어있는 경우, 현재 운석을 스택에 추가합니다(stack.push(asteroid)). 이는 음수 크기의 운석이 스택에 살아남은 경우입니다.
- stack에는 충돌을 피해남으로써 남아 있는 운석들이 저장되어 있습니다. 이들을 새로운 배열에 저장하여 반환합니다.
- stack.size()를 통해 남아 있는 운석들의 개수를 알아냅니다.
- result 배열을 생성하고, 스택에서 운석들을 꺼내어 뒤에서부터 result 배열에 저장합니다.
- 최종적으로 result 배열을 반환합니다.
Test
package io.lcalmsky.leetcode.asteroid_collision;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
class SolutionTest {
@Test
public void givenAsteroids_whenCollide_thenFindOutTheStateOfTheAsteroids() {
assertAll(
() -> test(new int[]{5, 10, -5}, new int[]{5, 10}),
() -> test(new int[]{8, -8}, new int[]{}),
() -> test(new int[]{10, 2, -5}, new int[]{10}),
() -> test(new int[]{-2, -1, 1, 2}, new int[]{-2, -1, 1, 2})
);
}
private void test(int[] given, int[] expected) {
// when
Solution solution = new Solution();
int[] actual = solution.asteroidCollision(given);
// then
assertArrayEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 64. Minimum Path Sum (0) | 2023.08.21 |
---|---|
[LeetCode] 2095. Delete the Middle Node of a Linked List (0) | 2023.08.02 |
[LeetCode] 2390. Removing Stars From a String (0) | 2023.07.31 |
[LeetCode] 2352. Equal Row and Column Pairs (0) | 2023.07.30 |
[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element (0) | 2023.07.29 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- @ManyToOne
- JSON
- spring boot app
- Spring Boot JPA
- Spring Boot
- QueryDSL
- 함께 자라기 후기
- intellij
- Java
- Spring Boot Tutorial
- proto3
- Linux
- spring boot application
- Spring Data JPA
- 스프링부트
- 알고리즘
- 스프링 부트 회원 가입
- gRPC
- spring boot jwt
- 스프링 부트 튜토리얼
- JPA
- 스프링 부트
- 클린 아키텍처
- 스프링 부트 애플리케이션
- r
- 스프링 데이터 jpa
- leetcode
- 헥사고날 아키텍처
- 함께 자라기
- Jackson
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
글 보관함