일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 332
- PCCP
- 카드 짝 맞추기
- 주사위 고르기
- DFS
- 2251
- SW아카데미
- 미로 탈출 명령어
- 847
- Eliminate Maximum Number of Monsters
- 백준
- leetcode
- 셔틀버스
- BFS
- reconstruct itinerary
- 구현
- 자바
- 양궁대회
- 주사위고르기
- 백트래킹
- Shortest Path Visiting All Nodes
- Java
- 알고리즘
- 소셜 광고
- 표편집
- 리트코드
- Number of Flowers in Full Bloom
- n+1카드게임
- 프로그래머스
- Heap
Archives
- Today
- Total
알고리즘이 재미있다
[LeetCode] 1921 - Eliminate Maximum Number of Monsters(java) 본문
https://leetcode.com/problems/eliminate-maximum-number-of-monsters/
정렬을 이용한 간단한 문제이다.
핵심
몬스터를 1분에 1마리씩 잡을 수 있고, 각 몬스터의 거리와 스피드가 다르다. 즉 거리대비 빠르게 접근해 오는 몬스터부터 잡아야 한다.
정답 코드
import java.util.Arrays;
class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
double[] arrival = new double[dist.length];
for (int i = 0; i < dist.length; i++) {
arrival[i] = (double) dist[i] / speed[i];
}
Arrays.sort(arrival);
int result = 0;
for (int i = 0; i < arrival.length; i++) {
if (arrival[i] <= i) {
break;
}
result++;
}
return result;
}
}
해설
앞서 말한 대로 가장 위협적인 적부터 죽여야 한다.
그 말은 거리대비 스피드가 가장 빠른 몬스터부터 나오도록 정렬시킨다.
이후 i(지난 시간) 보다 작다면 게임이 종료된다.
배운 점
간단한 문제이지만 접근법에 따라 난이도가 달라진다.
나는 처음에 1분이 지날 때마다 몬스터의 거리를 줄여야 하는 것 아닌가 하는 생각이 들었지만
이보다 더 편한 방법이 있다는 것을 생각하고 쉽게 풀 수 있었다.
사실 이미 처음 생각한 방법은 시간복잡도 때문에 잘못되었다고 생각했다.
간단한 문제라도 더 쉽게 풀 수 있는 아이디어를 많이 배우는 것 같다.