[LeetCode] 1921 - Eliminate Maximum Number of Monsters(java)

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

Eliminate Maximum Number of Monsters - LeetCode

 

정렬을 이용한 간단한 문제이다.

 

핵심

몬스터를 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분이 지날 때마다 몬스터의 거리를 줄여야 하는 것 아닌가 하는 생각이 들었지만

이보다 더 편한 방법이 있다는 것을 생각하고 쉽게 풀 수 있었다.

사실 이미 처음 생각한 방법은 시간복잡도 때문에 잘못되었다고 생각했다.

 

간단한 문제라도 더 쉽게 풀 수 있는 아이디어를 많이 배우는 것 같다.