[Java] LeetCode 1921. Eliminate Maximum Number of Monsters

[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;
    }
}