(Python3) - LeetCode (Medium) : 2593. Find Score of an Array After Marking All Elements

https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements

📕 풀이방법

📔 입력 및 초기화

1. 우선순위 큐 pq, 정답 score, check 여부 ck배열 선언 후 적절히 초기화합니다.

 

2. nums의 원소를 순회하면 값, index정보를 pq에 저장합니다.

📔 풀이과정

min heap인 pq의 원소에 대해 while lop를 수행하며 다음을 진행합니다.1. 이미 check되어 있다면 continue 합니다.

 

2. check가 안된 원소를 score에 더하고 인접 index를 범위를 넘지 않았다면 check해줍니다.

 

pq의 길이 n개 만큼 while loop를 진행해 인접 원소를 pop후 check해주므로 우선순위큐에 원소 삽입, 삭제 O(logn)을 곱한  O(nlog(n))이 시간복잡도가 됩니다.

 

📔 정답 출력 | 반환

score를 반환합니다.

---

📕 Code

📔 Python3

from heapq import heappush, heappop
class Solution:
    def findScore(self, nums: List[int]) -> int:
        pq = []
        score = 0
        ck = [0] * len(nums)
        for i, n in enumerate(nums):
            heappush(pq,(n,i))
        while pq:
            num, index = heappop(pq)
            if ck[index] == 1:
                continue
            score += num
            ck[index] = 1
            if index - 1 >= 0:
                ck[index-1] = 1
            if index + 1 < len(nums):
                ck[index+1] = 1

        return score

---

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