Medium - Find Score of an Array After Marking All Elements

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

Find Score of an Array After Marking All Elements - LeetCode

문제 설명

You are given an array nums consisting of positive integers.

Starting with score = 0, apply the following algorithm:

• Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
• Add the value of the chosen integer to score.
• Mark the chosen element and its two adjacent elements if they exist.
• Repeat until all the array elements are marked.

Return the score you get after applying the above algorithm.

Constraints:

• 1 <= nums.length <= 10 ** 5
• 1 <= nums[i] <= 10 ** 6

예시

Input: nums = [2,1,3,4,5,2]
Output: 7
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [x,x,x,4,5,2].
- 2 is the smallest unmarked element, so we mark it and its left adjacent element: [x,x,x,4,x,x].
- 4 is the only remaining unmarked element, so we mark it: [x,x,x,x,x,x].
Our score is 1 + 2 + 4 = 7.

Input: nums = [2,3,5,1,3,2]
Output: 5
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,x,x,x,2].
- 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [x,x,x,x,x,2].
- 2 is the only remaining unmarked element, so we mark it: [x,x,x,x,x,x].
Our score is 1 + 2 + 2 = 5.

풀이

class Solution:
    def findScore(self, nums: List[int]) -> int:
        length = len(nums)
        table = [False, ] * length
        ret = 0
        sorted_num_idx = sorted([(val, i) for i, val in enumerate(nums)])

        for num, idx in sorted_num_idx:
            if table[idx]:
                continue
            
            if idx > 0:
                table[idx-1] = True
            if idx < length - 1:
                table[idx+1] = True
            ret += num

        return ret

왼쪽에서부터, 가장 작은 숫자 등 풀이에 도움이 되는 조건이 있어서 다행인 문제.

숫자와 인덱스를 오름차순으로 정렬하고, 사용된 숫자의 인덱스는 배열 혹은 해쉬맵을 통해서 다음 루프에서는 생략하도록 표시한다.