LeetCode - 1921. Eliminate Maximum Number of Monsters

https://leetcode.com/problems/eliminate-maximum-number-of-monsters/description/

Eliminate Maximum Number of Monsters - LeetCode

leetcode - Eliminate Maximum Number of Monsters

문제 유형 : 정렬

문제 난이도 : Medium

 

문제

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.

 

당신은 n개의 몬스터로부터 도시를 지키는 게임을 하고 있습니다.

당신은 n개의 크기의 0-인덱스 배열 dist와 speed를 받습니다. 처음 몬스터는 dist만큼 떨어져있고, 각 몬스터는 분당 speed만큼의 속도로 다가옵니다.

당신은 한 마리의 몬스터를 완전 충전된 무기로 공격해서 제거할 수 있습니다.

그러나, 완충되는 데에는 1분이 걸립니다.

몬스터가 도착하면 게임에서 패배합니다.

최대한 잡을 수 있는 몬스터의 수를 구하시오.

 

 

풀이

시간 배열을 따로 만들어줍니다. 시간 = 속력 / 거리.

그렇게 각 도착시간이 담긴 배열을 오름차순 정렬합니다.

잡은 수를 0으로 시작하고, i를 단위로 루프를 돕니다.

만약 times[i]보다 i가 크거나 같으면 시간 내로 잡지 못한다는 뜻으로 킬 수를 반환합니다.

루프 한번마다 잡은 수를 1씩 누적시키고, 배열 순환이 끝나면 잡은 수를 반환합니다.

 

 

코드

C++

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int n = dist.size();
        vector<double> times(n);

        for (int i = 0; i < n; i++) {
            times[i] = (double)dist[i] / speed[i];
        }

        sort(times.begin(), times.end());

        int killed = 0;
        for (int i = 0; i < n; i++) {
            if (times[i] <= i) {
                return killed;
            }
            killed++;
        }

        return killed;
    }
};