[코딩/LeetCode150-(4)] Remove Duplicates from Sorted Array II(80)

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python을 사용합니다.

 

 

 

난이도: MEDIUM

키워드: Array, Two-Pointers

 

문제

문제원문: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150 

 

주어진 감소하지 않는 순서로 정렬된 정수 배열 nums이 주어졌을 때, 동일한 값이 최대 두번만 반복되도록 in-place형태로 nums를 업데이트해라. (다시 말해, 3번 이상 중복된 값은 제거해라) 이 때 값들의 상대적인 순서는 유지되어야한다. 최종적으로 수정된 nums 배열 내에 있는 원소의 개수를 반환하라.

 

단, 추가적인 배열 등을 이용한 메모리 사용이 다음과 같이 제한된다. 다시 말해, 추가 메모리 사용은 O(1)으로 제한된다.

 

 

문제 풀이 (Runtime: 98.36% Beat, Memory: 54.08 %)

 

이 문제는 앞선 26번 문제 와 크게 다르지 않습니다. 그래서 난이도가 MEDIUM이라고 명시되어있지만 그렇게 어려운 문제는 아닙니다. 애초에 26번 문제를 풀때 저는 추가 메모리를 사용하지 않았어서 특히 더 어렵지 않다고 생각됐습니다. 

 

저는 두 개의 pointer를 사용해서 문제를 해결했습니다. left 커서의 경우 in-place로 편집할 위치를 나타내며 right 커서는 배열을 조회하는 역할을 합니다. 따라서 right 커서가 모든 배열을 순회하면 종료됩니다.

 

주어진 배열은 이미 sorting되어있기 때문에 별도의 메모리를 사용하지 않고도 앞선 2개의 원소를 조회하여 문제를 해결할 수 있습니다. 만약 배열에 넣고자하는 위치의 직전 값과 2개 앞선 곳의 값이 right 커서의 값과 같다면 해당 원소는 뛰어넘어주어야합니다. 반면 이에 해당하지 않으면 left 위치에 해당 값을 옮겨 적고 left 커서와 right 커서를 각각 1씩 증가시키면됩니다. 최종적으로 right 커서의 순회가 끝나면 left 커서가 가르키는 인덱스 값이 우리가 얻고자하는 수정된 배열의 길이를 나타냅니다.

 

이때, 배열의 indexing error는 배열의 길이가 2 이하인경우는 배열의 길이를 반환하는 형태로 쉽게 처리할 수 있습니다.

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:

        if len(nums) == 1:
            return 1
        
        if len(nums) == 2:
            return 2

        left, right = 2, 2

        while right < len(nums):
            if nums[left-1] == nums[right] and nums[left-2] == nums[right]:
                right += 1
            else:
                nums[left] = nums[right]
                left += 1
                right += 1
        
        return left

 

 

📚 LeetCode 75 / Code Signal 풀이 보러가기