[LeetCode] 2251 - Number of Flowers in Full Bloom(java)

https://leetcode.com/problems/number-of-flowers-in-full-bloom/

LeetCode - The World's Leading Online Programming Learning Platform

현재의 people 위치에서 꽃이 몇 개가 있는지를 체크하는 문제이다.

매우 단순한 방법으로 브루트포스를 생각할 수 있지만, 시간복잡도 때문에 우선순위 큐를 활용하여 풀 수 있었다.

 

 

핵심

문제의 요구 사항에 꽃의 총길이 5 * 10^4이고, 시작점부터 끝점까지 최대 차이는 10^9이다.

또한 사람의 길이도 5 * 10^4이다. 꽃의 모든 위치를 적어주며 업데이트하는 방식은 사용할 수가 없다.(최소 5 * 10^4 *10^9)

따라서 힙을 사용하여 푸는 방식을 사용하였다.(5*10^4 * 5*10^4)

 

 

정답 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int[] sortedPeople = Arrays.copyOf(people, people.length);
        Arrays.sort(sortedPeople);

        Arrays.sort(flowers, Arrays::compare);
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int now = 0;
        for (int p : sortedPeople) {
            while (now < flowers.length && flowers[now][0] <= p){
                pq.add(flowers[now][1]);
                now++;
            }

            while (!pq.isEmpty() && pq.peek() < p){
                pq.remove();
            }
            map.put(p, pq.size());
        }

        int[] result = new int[people.length];
        for (int i = 0; i < people.length; i++) {
            result[i] = map.get(people[i]);
        }

        return result;
    }
}

해설

코드 자체가 매우 직관적으로 잘 나타나있어서 해석이 어렵지는 않다.

원래 사람의 위치대로 리턴을 해줘야 하므로, sort 시킨 위치를 복사해서 만들어준다.

또한 꽃의 값이 작은 것부터 나오도록 sort 시켜준다.

map은 사람의 원래 위치에 대한 값을 리턴해주기 위해 사용되고, pq는 현재 꽃을 담고 있는 그릇이다.

 

현재 사람의 위치를 sort 시켰기에 now 값을 줄일 필요가 없이 그대로 탐색하면 된다.

사람의 위치가 now꽃의 시작점보다 크면 꽃을 pq에 담고, now를 증가시켜서 다음 꽃을 확인한다.

이후에 꽃의 종료점이 현재 사람의 위치보다 작은 것은 제거해 준다. 이때 pq의 사이즈가 남은 꽃의 개수이다.

 

마지막으로 각 인덱스에 해당하는 사람의 위치를 원래 위치대로 복원해서 반환해 준다.

 

배운 점

문제를 보자마자 매우 직관적이라 문제를 이해하는데 어렵지 않았다.

다만 시간복잡도의 문제가 있기에 단순한 방법으로는 풀 수 없었다.

처음에는 heap도 시간복잡도에 걸릴 것이라 생각했는데, people도 정렬을 하고 진행하니 쉽게 해결할 수 있었다.