leetcode medium : Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II - LeetCode

Remove Duplicates from Sorted Array II - LeetCode

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = len(nums)
        
        number = nums[0]
        count = 1
        
        for i in range(1, len(nums)):
            if nums[i] == number:
                count += 1
                
                if count > 2:
                    nums[i] = 30001
                    k -= 1
            else:
                number = nums[i]
                count = 1
                
        nums.sort()
        
        return k

 

처음 짠 코드는 이거다.

2번 초과해서 나타나는 수는 nums[i]의 최대치 30000보다 큰 30001로 바꾸고

전체 array를 sort하는 방식. 파이썬 리스트 메서드 sort는 in-place이기 때문에 O(N log N) 타임으로 문제를 해결할 수 있다. 흠 근데 문제가 두 가지 있다.

첫 번째, 메서드 내장 sort 함수를 못 쓰는 경우라면? 특히 파이썬이 아니라 다른 언어면 어떡할 것인가?

두 번째, submission 결과를 보니 8%의 submission을 time측면에서 이겼다고 나왔다. 즉 92%보다 느리다는것. 뭔가 더 빠른 로직이 있어야한다.

 

내가 처음으로 푼 이 solution은 optimal이 아니라는 결론에 이르렀고 O(N) 솔루션이 있나 고민해보게 되었다.

내가 생각한 해답은 이렇다. pointer를 두개 두는 two pointers 전략!

각각의 포인터는 read용과 write용이고 read포인터에서 읽은 값을 write 포인터에 쓰는 방식이다. 근데 중복이 3개 이상 발생함을 감지하면 read포인터를 다음숫자까지 쭉 증가시켜주는거다. 그리고 그 다음숫자를 write포인터에 쓰는식으로.. 쉽게말하면 연속된 숫자가 3개 이상 있으면 포인터를 뒤쪽으로 쭉 보내서 다음숫자를 지금 위치로 가져오는거다. 이렇게하면 O(N)으로 해결이 가능하다.

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = len(nums)
        
        number = nums[0]
        count = 1
        
        i = 1 #read pointer
        j = 1 #write pointer
        while i < len(nums):
            if nums[i] == number:
                count += 1
                
                if count > 2:
                    while i < len(nums) and nums[i] == number:
                        i += 1
                        k -= 1
                    if i == len(nums):
                        break
                    else:
                        number = nums[i]
                        count = 1
            else:
                count = 1
                number = nums[i]
            
            nums[j] = nums[i]
            j += 1
            i += 1
        
        return k

 

자 근데 if문이 세 개나 중첩되었다. 리팩토링을 좀 해야겠지? ><

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 1
        number = nums[0]
        k = 1
        
        for i in range(1, len(nums)):
            if nums[i] == number:
                count += 1
            else:
                number = nums[i]
                count = 1
                
            if count > 2:
                continue
            
            nums[k] = nums[i]
            k += 1
            
        return k

 

코드가 훨씬 읽기 쉽고 간결해졌다. 근데..ㅠㅠㅠ

시간 왜저럼?ㅠㅠㅠ 하..

 

for문 말고 while로 바꿔볼까 같은로직으로..

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 1
        number = nums[0]
        k = 1
        
        i = 1
        while i < len(nums):
            if number == nums[i]:
                count += 1
            else:
                number = nums[i]
                count = 1
                
            if count > 2:
                i += 1
                continue
                
            nums[k] = nums[i]
            k += 1
            
            i += 1
            
        return k

 

좀 나아졌네.. 역시 근데 count가 2 초과될 때 안에 while문 써서 i를 쭉 늘려주는게 젤 좋으려나

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 1
        number = nums[0]
        k = 1
        
        i = 1
        while i < len(nums):
            if number == nums[i]:
                count += 1
            else:
                number = nums[i]
                count = 1
                
            if count > 2:
                while i < len(nums) and nums[i] == nums[i - 1]:
                    i += 1
                continue
                
            nums[k] = nums[i]
            k += 1
            
            i += 1
            
        return k

 

성능이 확 뛰긴 하네.

바깥쪽 while문에 의해 발생하는 제어이동을 줄여서 오버헤드가 더 적어지는거같다.

같은 알고리즘인데도 어떻게 쓰느냐에 따라 성능차이가 나네.

결국 중첩이 팍팍 되는건 피할수 없었구만.

다른 사람들 코드를 볼까?

 

def removeDuplicates(self, nums):
    i = 0
    for n in nums:
        if i < 2 or n != nums[i-2]:
            nums[i] = n
            i += 1
    return i

 

??????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????

??????????????????????????????????????????????????????????????????????????????????????

 

진짜 매번 느끼는건데 LeetCode 문제들의 Discussion 게시판에는 God of code들만 모여있다;;

와 이게 이렇게 간단하게 작성될 수 있는거였다고?;;;

어..음.. 해석을 해보자?

i는 write용 포인터다. 그니까 nums[i] = n 이런식으로 쓰겠지.

for n in nums로 nums의 모든 숫자를 체크한다.

i가 <2이면 즉, 아직 쓴 숫자가 2개를 넘지 않으면 그냥 nums[i]에 n을 써버린다.

같은 숫자가 연속해서 나온다해도 2개까지는 허용되니까 그냥 써버려도 된다 i < 2일때는.

자 그럼 i >= 3일때는 어떻게 되나?

nums[i-1]랑 nums[i-2]랑 n이 중복된 숫자면? 셋이 다 같겠지? 그니까 nums[i-2] != n 조건에 걸린다.

nums[i-1]랑 nums[i-2]랑 같고 n이 새 숫자면? nums[i-2]랑 n은 다르니까 조건이 만족해서 nums[i] = n이 수행된다

셋이 다 다른 숫자면? nums[i-2]랑 n은 당연히 다르니까 nums[i] = n이 수행된다.

애초에 중복이 3개 이상 발생해야만 nums[i-2]가 n과 같아진다. 

 

아 이건 진짜 미쳤다.. 모르겠다 난 코딩 너무 못하는거같다;;............에횽