일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- programmers
- 부분배열
- string
- ArrayList
- 리트코드
- 우선순위 큐
- dfs
- 알고리즘
- hashset
- Algorithm
- recursion
- 깊이우선탐색
- HashMap
- two pointers
- binary tree
- leetcode
- Array
- greedy
- 재귀함수
- 브루트포스
- PCCP
- priority queue
- DP
- coding
- Java
- Today
- Total
지식창고
[Java] LeetCode 1921. Eliminate Maximum Number of Monsters 본문
[Java] LeetCode 1921. Eliminate Maximum Number of Monsters
junz 2023. 11. 7. 10:22[Java] LeetCode 1921. Eliminate Maximum Number of Monsters
문 제 :
몬스터와 city 사이의 거리를 나타낸 정수 배열 dist[],
각 몬스터의 턴 당 속도를 나타낸 정수 배열 speed[] 가 주어진다.
몬스터가 city에 도착하게 되면 게임에서 지게된다.
한 턴에 한 몬스터를 죽일 수 있다.
지기 전까지 최대한 몬스터를 많이 잡아보려고 한다.
최대로 잡을 수 있는 몬스터의 수를 반환해라.
Constraint
{ n == dist.length == speed.length }
{ 1 <= n <= 10^5 }
{ 1 <= dist[i], speed[i] <= 10^5 }
Matter
You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the ith monster from the city.
The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the ith monster in kilometers per minute.
You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge. The weapon is fully charged at the very start.
You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.
Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.
Example )
Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.
=======================================================================================
Example 2:
Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.
=======================================================================================
Example 3:
Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.
해 결 & 설 명:
각 몬스터가 몇 턴만에 city에 도착하는가? 를 이용하는게 키 이다.
저 정보를 가지는 배열을 만들어주고, 오름차순으로 정렬해준다.
그러면 가장 빨리 도착하는 몬스터 순서대로 정렬이 될 것이다.
즉, 가장 먼저 없애야 할 몬스터 순서 리스트가 되는 것이다.
결 과 :
class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
// n마리의 몬스터
// n마리의 몬스터의 city와의 거리 dist[]
// n마리의 몬스터의 km/m 속도 speed[]
// 한번의 공격으로 한마리의 몬스터 킬 - 1분에 한발
// 몬스터가 city에 다다르면 lose. 몬스터가 다다르는 시점에 무기쿨이 돌아도 진 판정
// 지기 전에만 무기 사용 가능
// 내가 지기 전에 최대 몇 마리의 몬스터를 잡을 수 있는지 리턴 -> 다 잡을수있으면 n리턴
// Greedy 접근 - 가장 가까운 적부터 제거
// 매 분마다 city와 가장 가까운 적을 제거해야함 - 속도가 각각 다르다.
// 각 몬스터가 몇 턴만에 도착하는지 저장하면 ? -> 해결
int result = 0;
int n = dist.length;
int[] turn = new int[n];
for(int i=0; i<n; i++) {
turn[i] = dist[i] / speed[i];
if(dist[i] % speed[i] > 0) turn[i]++;
}
Arrays.sort(turn); // 제거해야 할 순서대로 정렬
// 앞부터 순회하면서 하나씩 제거 -> 만약 현재 턴보다 작은턴이면? city에 도착했다는 말
for(int i=0; i<n; i++) {
if(turn[i] > i) {
result++;
}
else {
break;
}
}
return result;
}
}
'Algorithm > Leetcode' 카테고리의 다른 글
[Java] LeetCode 2849. Determine if a Cell Is Reachable at a Given Time (0) | 2023.11.08 |
---|---|
[Java] LeetCode 347. Top K Frequent Elements (0) | 2023.05.23 |
[Java] LeetCode 1721. Swapping Nodes in a Linked List (0) | 2023.05.15 |
[Java] LeetCode 2405. Optimal Partition of String (0) | 2023.04.05 |
[Java] LeetCode 1402. Reducing Dishes (0) | 2023.03.29 |