티스토리 뷰

문제 링크 : https://leetcode.com/problems/most-beautiful-item-for-each-query/description/

🍊해결방법

  • queries에 있는 price보다 잦은 값 중에서 최대 beauty 값을 찾는 것이다
  • items 배열을 정렬하자
  • price를 오름차순으로 하면서 beauty는 내림차순으로 해서 beauty값을 계속 최대값으로 갱신하자
  • queries의 price 값을 가지고 이진탐색을 통해 items에서 찾자

😀풀이

import java.util.*;

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {


        // price순으로 오름차순을 하고 같은 가격일 때는 beauty가 높은순으로 정렬
        // 이렇게 정렬된 상태로 각 price일 때 최대치를 저장
        // queries의 값을 이진탐색을 통해서 찾자

        Arrays.sort(items, (o1,o2)->{
            if(o1[0] == o2[0])
                return o2[1] - o1[1];
            else
                return o1[0] - o2[0];
        });


        // 최대값을 저장하자
        int max = items[0][1];

        for(int i=1; i<items.length; i++){

            int beuty = items[i][1];

            if(max > beuty){
                items[i][1] = max;
            }
            else{
                max = beuty;
            }
        }


        // 이제 queries를 돌면서 찾자
        for(int i=0; i<queries.length; i++){

            int num = queries[i];

            int s = 0;
            int e = items.length-1;

            int ans = -1;
            while(s <= e){

                int mid = (s+e)/2;

                if(items[mid][0] <= num){
                    s = mid + 1;
                    ans = mid;
                }
                else{
                    e = mid - 1;
                }

            }
            
            if(ans != -1)
                queries[i] = items[ans][1];
            else
                queries[i] = 0;

        }


        return queries;
    }
}