leetcode 1695. Maximum Erasure Value

leetcode May Challenge 28 - Maximum Erasure Value

---

 

leetcode - Maximum Erasure Value

결과적으로, 이 문제는 시간 복잡도가 O(N)만에 풀이할 수 있는 풀이법으로 풀이해주었다.

 

문제는 위와 같이 배열이 주어졌을 경우, 중복 값을 가지지 않는 연속된 부분 배열 중 그 배열의 요소의 합이 가장 큰 경우의 합을 출력하는 것이었다.

 

그리고 문제 조건을 보면 nums의 길이가 최대 10,000 이기 때문에 완전 탐색은 당연하게도 절대 불가능했다. 그리고 처음엔 투포인터로 접근해 left와 right을 증가시켜주며 합을 기억하고, 중복 값이 발견되는 경우를 set을 통해서 검출해주는 방식으로 접근했지만, 중복값을 검출했을 경우 left를 어떻게 갱신해주어야 최적화가 되는지 찾아내지 못하여 시간이 조금 걸린 문제였다.

 

결론적으로, nums의 각 요소들을 순회하며 중복인지 아닌지 체크해주며 (여기서는 배열로 체크해주었다) total이라는 변수에 현재까지의 누적 합을 구해나갔다. 그리고 그 과정에서 만약 중복이라면, 대기하고 있던 left가 하나씩 오른쪽으로 전진하며 중복 값을 풀어줌과 동시에 누적 합에서 그 요소만큼을 빼주었다.

 

이렇게 중복을 해제하는 과정에서(0으로 바꾸어 주는 과정에서) 만약 현재 가리키고 있는 수의 중복을 해제했다면 이제 다시 누적합을 구해나갈 준비가 되었다는 뜻이다. 왜냐하면 유니크한 부분 배열이라는 조건을 이미 중복을 해제했을 때 만족하기 때문이다.

[5, 2, 1, 2, 5, 2, 1, 2, 5]

# 4 번째 '5'를 순회할 차례일 때, left가 0번째 '5'를 중복 해제해주었다면
# 다시 1번째 '2'부터의 누적 합을 구해나갈 준비가 되었다는 뜻이다.

위의 예시에서, 4번째 '5'를 순회하는 차례일 때 누적 합은 총 15이다. 하지만 5는 이미 중복된 수이기 때문에 left가 오른쪽으로 이동하는 과정에서 5의 중복 사실을 해제하며 누적 합에서 5를 빼줄 것이다.

 

그렇다면 현재 left가 보는 수는 2이며, 그 때의 누적 값은 10(15 - 5)이 된다. 즉, 1번째 ~ 4번째까지의 누적 합인 10을 가지고 있게 되는 것이고 이 값은 우리가 원했던 값이므로 접근 방법이 올바르다는 것이다.

 

아래 풀이의 경우, 시간 복잡도는 O(N)이 된다.

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return nums[0]
        
        used = [0] * 10001
        left, total, ans = 0, 0, 0
        
        
        for right in nums:
            total += right
            
            if not used[right]:
                used[right] = 1
                
            else:
                while used[right]:
                    total -= nums[left]
                    used[nums[left]] = 0
                    left += 1
                
                used[right] = 1
            
            ans = max(ans, total)
        
        return ans
        

제출 결과

 

https://leetcode.com/problems/maximum-erasure-value/

Maximum Erasure Value - LeetCode