[코테연습] 2070. Most Beautiful Item for Each Query

이진탐색 / 정렬 / 배열문제

문제 분석

• 각 아이템은 [price, beauty] 형식으로 주어지며, price는 가격, beauty는 아름다움을 나타냅니다.
• 각 쿼리 값에 대해 price가 쿼리 값 이하인 아이템 중 beauty가 가장 높은 값을 찾아야 합니다.
• 특정 가격 이하의 최대 beauty 값을 빠르게 찾기 위해 효율적인 접근 방식이 필요합니다.
• 답이 없는 경우, 즉 가격 조건을 만족하는 아이템이 없을 경우, 해당 쿼리의 결과는 0입니다.

문제 풀이

1. 아이템 정렬:
   • price를 기준으로 오름차순으로 정렬합니다.
   • 이렇게 하면 낮은 가격에서 높은 가격으로 순차적으로 beauty 값을 비교할 수 있습니다.
2. 누적 최대 beauty 값 추적:
   • 각 아이템을 순회하며 현재까지의 beauty의 최댓값을 계산하여 누적 저장합니다.
   • 누적된 {price, maxBeauty} 쌍을 리스트에 저장합니다. 이 리스트는 가격이 증가할수록 beauty의 최댓값이 갱신된 결과를 포함하게 됩니다.
3. 이진 탐색을 활용한 쿼리 처리:
   • 각 쿼리에 대해 이진 탐색을 사용하여 쿼리 가격 이하의 최대 beauty 값을 찾습니다.
   • 이진 탐색을 통해 쿼리 가격보다 작거나 같은 price의 최댓값을 찾고, 해당 가격의 beauty 값을 반환합니다.
4. 결과 반환:
   • 각 쿼리의 결과를 배열로 반환합니다.

 

> java

 

public class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        // items 배열을 price 기준으로 오름차순 정렬
        Arrays.sort(items, (a, b) -> a[0] - b[0]);

        // 누적 최대 beauty 값을 저장할 리스트
        List<int[]> maxBeauties = new ArrayList<>();
        int maxBeauty = 0;

        // price에 따른 누적 최대 beauty 값을 계산
        for (int[] item : items) {
            int price = item[0];
            int beauty = item[1];
            maxBeauty = Math.max(maxBeauty, beauty);
            maxBeauties.add(new int[]{price, maxBeauty});
        }

        // 결과를 저장할 배열
        int[] result = new int[queries.length];

        // 각 쿼리에 대해 이진 탐색을 수행
        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            
            // 해당 query 이하의 최대 beauty 값을 찾기 위해 이진 탐색
            int idx = binarySearchRight(maxBeauties, query);
            
            if (idx >= 0) {
                result[i] = maxBeauties.get(idx)[1];
            } else {
                result[i] = 0;
            }
        }

        return result;
    }

    // 이진 탐색을 통해 query 이하의 최대 price를 가진 인덱스를 찾는 함수
    private int binarySearchRight(List<int[]> maxBeauties, int query) {
        int left = 0, right = maxBeauties.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (maxBeauties.get(mid)[0] <= query) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return right;
    }
}

 

 

> python

 

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        # price를 기준으로 오름차순으로 정렬
        items.sort()
        
        # price에 따라 누적 최대 beauty 값을 저장
        max_beauties = []
        max_beauty = 0
        for price, beauty in items:
            max_beauty = max(max_beauty, beauty)
            max_beauties.append((price, max_beauty))
        
        # 쿼리 결과를 저장할 리스트
        result = []
        
        # 각 쿼리에 대해 해당 가격 이하의 최대 beauty 값을 이진 탐색으로 찾음
        for query in queries:
            idx = bisect_right(max_beauties, (query, float('inf'))) - 1
            # 유효한 인덱스라면 최대 beauty 값을 추가, 아니면 0을 추가
            if idx >= 0:
                result.append(max_beauties[idx][1])
            else:
                result.append(0)
        
        return result