[리트코드 leetcode] 2576. Find the Maximum Number of Marked Indices (파이썬/Python)

 

목차

개요

Find the Maximum Number of Marked Indices - LeetCode

nums 배열이 주어진다. 이 배열에서 위 수식을 만족하는 인덱스 쌍에다 마크를 칠할 것이다. 한번도 마크되지 않은 쌍만 쌍이 될 수 있다. 이런 쌍이 최대 몇 개까지 나올 수 있는지 반환하라.

풀이

처음에는 그냥 최대 원소를 반환하라는 줄 알고 조금 헤맸다. 
결국 쌍을 찾으면 되는 문제이고 그 쌍의 최대값은 nums 배열의 절반일 것이다.

그 점에서 착안해서 문제를 접근하자. 어차피 어떤 배열이 들어와도 정답의 최대값은 해당 배열의 길이의 절반이다.
위의 정렬된 배열에서 i와 j쌍(i는 j보다 작다)을 찾는다고 생각을 해보자면 c가 i가 되는 경우가 있을까? c가 i로써 한 쌍에 속하는 경우는 나올 수 있다. 1,2,3,4,6이라는 배열이 있다면 3,6이라는 쌍이 만들어질 것이다. 그러나 해당 배열에서는 꼭 c가 쌍이 되지 않더라도 정답, 즉 쌍 개수는 2개로 동일하다. 

무슨 말이냐, 어떤 배열을 받았을 때 그것을 정렬하고 나면 중앙값과 그보다 큰 값들은 쌍에 속하더라도 작은 값으로서 쌍에 속하지 않는다는 것이다. 이걸 감안한다면 투포인터 알고리즘을 사용할 수 있다.

코드

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        n = len(nums)
        inlst = sorted(nums)
        ans = 0
        i, j = 0, n // 2
        while i < n//2 and j < n:
            if inlst[i] * 2 <= inlst[j]:
                ans += 2
                i += 1
            j += 1
        return ans