[코딩/LeetCode150-(3)] Remove Duplicates from Sorted Array (26)

 

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

 

 

 

난이도: EASY

키워드: Array, Two-Pointers

 

문제

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

 

 

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

 

 

문제 풀이 (Runtime Beats 81.92%, Memory Beats 88.81%)

 

이 문제 역시 Two-pointers 기법으로 쉽게 해결할 수 있다. In-place 방식이 아니라면 Counter를 써서 key()값을 반환하는 형태 등으로도 풀 수 있겠지만, 이 문제의 핵심은 In-place로 문제를 해결해야한다는 점이다. 이 문제는 사실상 27번 문제와 유사하다. 

 

다만 디테일이 조금 다르다. 연속되는 값인 경우 in-place하는 배열에 저장하면 안된다. 이를 위해서 현재 in-place하고자하는 커서인 left의 직전 값이 현재 탐색 커서 right의 값과 같은 경우 right는 전진 탐색하고 left의 정보는 업데이트 하지 않는 형태로 코드를 작성하였다. 다만 이 때 주의할 점은 left의 indexing이 left-1을 조회하기 때문에 초기 값을 0이아닌 1로 주어야하고, 이 때의 exception handling을 함께 해주었다. (배열의 길이가 1인경우 이전 값을 조회할 수 없으므로 길이와 함께 바로 반환)

 

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

        if len(nums) == 1:
            return 1

        left, right = 1, 1

        while right < len(nums):

            if nums[left-1] == nums[right]:
                right += 1
            else:
                nums[left] = nums[right]
                left += 1
                right += 1
        
        return left

 

Takeaway

• Two-pointers 

 

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