1423. Maximum Points You Can Obtain from Cards

문제 링크 : https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

배열의 양 끝 숫자 중 하나를 포함하는 길이 k의 연속된 부분 배열 중 그 합이 최대가 되는 부분 배열을 찾는 문제이다.

처음에 풀이 방법을 생각했을 때 양 끝쪽중에 가장 큰 수와 그 큰수를 제외한 나머지 중에서 가장 큰 경우를 더하는 방식으로 풀었는데

class Solution:
    def maxScore(self, nums: List[int], k: int) -> int:
        point = max(nums[0], nums[-1])
        nums.pop(point)
        window = sum(nums[:k-1])
        ans = window
        for i in range(k-1,len(nums)):
            window += nums[i] -nums[i-(k-1)]
            ans= max(ans, window)
        return point+ans

cardPoints = [9,7,7,9,7,7,9], k = 7

테케에서 범위가 벗어나서 실패했다.

cardPoints = [1,2,3,4,5,6,1], k = 3 를 예로 들어보자면

예를 들어 1,2,3,4를 제외하고 k의 범위만큼 5+6+1 의 합을 더하면 12이다. [1,2,3,4,/5,6,1]
그리고 다음으로 2,3,4,5를 제외한 범위인 1,6,1을 더한 값[1/2,3,4,5/6,1]은 아까 기존의 (5+6+1) 12에서 5가 빠지고 1이 추가된 값인 8이다.
그 다음으로 3,4,5,6을 제외한 범위인 1,2,1를 합한 값[1,2/3,4,5,6/1]은 아까 기존의 (1+6+1)을 더한 값에서 6을 빼고 2가 추가된 값이다.
마지막으로 4,5,6,1을 제외한 범위인 1,2,3을 합한 값은[1,2,3,4,5,6,1] 아까 값(1,2,1)에서 1을 빼고 3을 추가한 값과 같다

이 원리를 이용하여 기존 값에서 새로운 값만 더하기만 해주면 일일이 다 더할 필요 없이 효율적인 방법으로 문제를 풀 수 있다.

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        l, r = 0, len(cardPoints)-k
        window= sum(cardPoints[r:])
        ans = window
        
        while r<len(cardPoints):
            window += cardPoints[l] -cardPoints[l]
            l+=1
            r+=1
            ans = max(ans,window)
        return ans

(수정한 성공한 답안)

22.09.01 복습