알고리즘이 재미있다

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

카테고리 없음

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

javajohaha 2023. 11. 7. 12:37

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

 

Eliminate Maximum Number of Monsters - LeetCode

Can you solve this real interview question? Eliminate Maximum Number of Monsters - 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 initi

leetcode.com

 

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

 

핵심

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

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

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

 

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