(Python3) - LeetCode (Medium) : 1014. Best Sightseeing Pair.py

https://leetcode.com/problems/best-sightseeing-pair

heap또는 binary search를 사용해 풀어본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

values의 길이를 length로 저장, 정렬된 값을 저장할 배열 sorted_values, 정답 변수 max_score를 선언 후 적절히 초기화합니다.

📔 풀이과정

values의 원소를 순회하며 다음을 진행합니다.

values에서 values[i] + i값의 최댓값을 O(logN)만에 찾을 수 있다면 sorted_values의 마지막 원소 + values[j] - j값의 최댓값만 찾는다면 O(NlogN)만에 답을 찾을 수 있습니다. 다음 두 가지 방식을 생각해볼 수 있습니다.

 

1. sorted_values에 넣을 때마다 정렬 상태를 유지하는 insort로 정렬상태를 유지하면서 찾을 수 있습니다.

 

2. max_heap으로 values[i] + i값의 최댓값을 찾아줍니다.

📔 정답 출력 | 반환

max_score를 반환합니다.

---

📕 Code

📔 Python3 - Binary Search

from bisect import insort
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        length = len(values)
        sorted_values = []
        max_score = 0
        for j in range(len(values)):
            if sorted_values:
                max_i = sorted_values[-1]
                max_score = max(max_score, max_i + values[j] - j)

            insort(sorted_values, values[j] + j)
        return max_score

📔 Python3 - Max Heap

from heapq import heappush, heappop
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        length = len(values)
        sorted_values = []
        max_score = 0
        for j in range(length):
            if sorted_values:
                max_i = heappop(sorted_values)
                max_i = -max_i
                heappush(sorted_values, -max_i)
                max_score = max(max_score, max_i + values[j] - j)

            heappush(sorted_values, -(values[j] + j))
        return max_score

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.