Python으로 푸는 LeetCode 26. Remove Duplicates from Sorted Array (Easy)

중복을 제거한 Array의 원소의 수를 구하고

기존 배열에 순서대로 해당 값을 나열해야 한다.

leetcode에서 푼 문제 리스트 보기

leetcode에서 문제 보기

github에서 코드 보기

문제 풀이

이 문제는 결국 기존 배열은 건드리지 말고 중복을 제거한 배열의 길이를 구하고 그 원소들을 배열에 값만 바꾸면 풀 수 있다. 배열의 변수에는 배열의 시작 주소가 담겨있다. 그리고 배열에 담긴 요소들의 길이마다 다음 원소의 주소값을 계산할 수 있다는 장점이 있다. 따라서 nums 변수에 다시 다른 배열에 할당했거나 배열의 길이를 늘렸다면 알아차릴 수 있으니 in-place 방식으로 문제를 풀라는 의미이다. 나는 문제를 쉽게 풀기 위해서 파이썬의 set 컨테이너에 담았다가 파이썬의 List 컨테이너로 다시 변경하여 정렬하는 방법으로 풀었기 때문에 상관이 없었다.

메모리나 시간을 고려하지 않고 문제를 빠른 시간 내에 푸는데 집중했기 때문에 코드를 제출하고 나서는 메모리와 시간을 고려하여 문제를 다시 풀었다. Index가 1인 경우부터 탐색을 시작하면서 Index-1 위치의 값과 서로 달라졌을 경우에 Index 1인 자리부터 차례대로 값을 채워넣어준다. 그 결과 중복되지 않은 원소들의 수는 앞에서부터 차례대로 채워지게 된다. 마지막으로 채워진 Index +1 만큼이 중복되지 않은 원소의 수이다. 

파이썬 코드

"""
LeetCode 2. Add Two Numbers
blog : https://daimhada.tistory.com/116
problem : https://leetcode.com/problems/add-two-numbers/submissions/
"""
 
class Solution:
    def removeDuplicates(self, nums) -> int:
        """
        Runtime : faster than 39.84% of Python3
        Memory Usage : less than 5.43% of Python3
        """
        temp = list(set(nums))
        temp.sort()
        for i, v in enumerate(temp):
            nums[i] = v
        return len(temp)
 
 
class Solution:
    def removeDuplicates(self, nums) -> int:
        """
        Runtime : fater than 79.66% of Python3
        Memory Usage : less than 5.43% of Python3

        """
        if len(nums) == 0:
            return 0
        change_index = 1
        for i in range(0, len(nums)):
            if i != 0 and nums[i - 1] != nums[i]:
                nums[change_index] = nums[i]
                change_index += 1
        print(change_index)
        return change_index
 
 
s = Solution()
s.removeDuplicates([0,1,1,2,3,4,4,4,4,4,5,6,7,8,9,11])  # 11
s.removeDuplicates([0,1,2,3,4,5]) # 6
s.removeDuplicates([-1]) # 1