Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

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

문제 요약

• input
  • nums: 비내림차순으로 정렬된 정수 배열
• nums 배열을 제자리에서 존재하는 원소들을 딱 하나만 남긴다.
• 초기의 정렬된 상태는 건드리지 않는다.

풀이

• nums.length는 최대 30_000이다. O(n^2)의 풀이는 불가능
• 먼저 nums에 존재한 원소의 개수를 센다.
• 개수가 1 이상인 원소에 한해서 nums 배열에서 제거한다. (하나는 남겨두어야 하므로 v - 1)
• 남은 nums의 길이를 리턴한다.

수도코드

def sol(nums):
	Counter = Counter(nums) # collections 라이브러리 이용
    
    for key, value in Counter.items():
    	for i=0..value-1:
        	nums에서 key 삭제
    return nums의 길이

Solution(runtime: 161ms)

from collections import Counter

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for k, v in Counter(nums).items():
            for _ in range(v - 1):
                nums.remove(k)
        
        return len(nums)

Solution(runtime: 80ms)

from collections import Counter

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        nums[:] = [e for e in cnt.keys()]
        return len(nums)

Counter는 nums 배열에 등장한 요소들의 개수를 저장한다.
따라서 key는 중복이 없는 set이므로 삭제 과정을 제거하고 추가만하도록 변경하였다. Counter에서 저장하는 과정은 O(n), 그리고 최대 200개의 key를 가질 수 있으므로 추가하는 과정에서는 크게 영향을 주지 않는다고 생각한다.