[Top Interview Questions] 26. Remove Duplicates from Sorted Array

정답)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 딕셔너리의 key에 유니크한 정수를 저장
        numDic = {nums[0]:1}
        k = 1
        
        for i in range(1, len(nums)):
        
            # 만약 새로운 유니크한 정수가 발견되면
            if nums[i] not in numDic:
            
                # 딕셔너리에 추가
                numDic[nums[i]] = 1
                
                # k에 1 더함
                k += 1
                
                # nums의 올바른 위치에 새로운 유니크한 정수 옮김
                nums[k-1] = nums[i]

        return k

문제)

문제출처

 

주어진 정수 배열 nums는 오름차순으로 정렬되어 있습니다. 반복되는 정수를 제거하여 그 정수가 한 번만 나오도록 하시오. 원래 nums에 나열되어있던 것처럼 정수들이 순서대로 나열되어있게 하시오.

 

nums에 남아있는 정수의 개수를 리턴하시오. 

 

유니크한 정수의 개수가 k라고 가정했을 때,

 

• k개의 정수가 nums의 맨 앞에, 순서대로 오도록 배치되어야 합니다. k개 이후의 원소들이나 nums의 크기는 중요하지 않습니다.
• k를 리턴하시오.

예시 1)

nums = [1, 1, 2]

output: 2, nums = [1, 2, _]

Explanation: nums에 유니크한 정수는 1, 2 뿐입니다. 그러므로 유니크한 정수의 개수 k는 2이죠. k개의 유니크한 정수를 제외한 나머지 숫자는 신경 쓰지 않아도 되므로 예시에선 밑줄이 사용되었습니다.

 

예시 2)

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Explanation: nums에 유니크한 정수는 0, 1, 2, 3, 4 뿐입니다. 그러므로 유니크한 정수의 개수 k는 5이죠. k개의 유니크한 정수를 제외한 나머지 숫자는 신경 쓰지 않아도 되므로 예시에선 밑줄이 사용되었습니다.

 

제한)

• 1 <= nums.length <= 3*10^4
• -100 <= nums[i] <= 100
• nums는 오름차순으로 정렬

풀이)

기본원리)

1. 딕셔너리에 첫 번째 유니크한 정수를 저장합니다.
2. nums를 선형검색하며 새로운 유니크한 정수가 있는지 확인합니다. 존재한다면 딕셔너리에 새로 추가해 주고 k의 값 또한 1 더해줍니다.
3. 새로운 정수를 nums의 올바른 위치에 옮겨줍니다.
4. 선형검색이 완료됐다면 마지막으로 k를 리턴합니다.

첫 번째 유니크한 정수)

numDic이라는 딕셔너리에 nums의 0번째 정수를 추가했습니다.

 

문제에서 nums의 길이가 1보다 크거나 작다고 했기 때문에 nums에는 적어도 1개의 유니크한 정수가 존재한다는 것을 알 수 있습니다.

 

그러므로 nums의 0번째 정수를 먼저 딕셔너리의 key에 추가해 줬습니다.(value는 사실 중요하지 않으므로 임의의 숫자 1을 추가해 줬습니다)

 

유니크한 정수가 한 개 존재하니 k 또한 1이 되야겠죠?

 

def removeDuplicates(self, nums: List[int]) -> int:
        numDic = {nums[0]:1}
        k = 1

새로운 유니크한 정수를 확인)

nums의 0번째 정수는 이미 확인했으니 1번째 정수부터 확인해 봅시다.

 

nums에 새로운 유니크한 정수가 보일 때마다 numDic에 추가해 줄 것입니다.

그래서 nums의 i번째 정수가 유니크한지 확인하려면 numDic의 key를 확인하면 됩니다.

 

만약 i번째 정수가 유니크하다면 numDic에 추가해 주고 유니크한 정수의 개수를 나타내는 k의 값 또한 1 더해줍니다.

 

def removeDuplicates(self, nums: List[int]) -> int:
        numDic = {nums[0]:1}
        k = 1
        
        for i in range(1, len(nums)):
            if nums[i] not in numDic:
                numDic[nums[i]] = 1
                k += 1

유니크한 정수 옮기기)

사실 이 부분을 생각하는 게 조금 힘들었습니다. k의 개수나 뭐가 유니크한지는 쉽게 알아낼 수 있지만 정수를 어느 위치로 옮겨야 되는지가 어렵더라고요.

 

그래서 생각한 게 k를 이용하는 것이었습니다.

 

nums[k-1]

이런 원리로 생각했을 때 nums[k-1]에 새로운 유니크한 원소를 옮겨서 위치를 업데이트해줬습니다.

유니크한 정수를 제외한 원소는 어떤 형식이든지 상관없다고 했으므로 건드려주진 않았습니다.

 

그렇게 선형검색이 끝나면 k를 리턴해줍니다.

 

def removeDuplicates(self, nums: List[int]) -> int:
        numDic = {nums[0]:1}
        k = 1
        
        for i in range(1, len(nums)):
            if nums[i] not in numDic:
                numDic[nums[i]] = 1
                k += 1
                
                nums[k-1] = nums[i]

        return k

디버깅)

nums = [1, 1, 2, 2, 2, 3, 3]

numDic = {1 : 1}

k = 1

 

(i = 1)    # numDic에 이미 1이 존재함

 

(i = 2)

numDic = {1 : 1, 2 : 1}

k = 2

nums = [1, 2, 2, 2, 2, 3, 3]

 

(i = 3)    # numDic에 이미 2가 존재함

(i =4)    # numDic에 이미 2가 존재함

 

(i = 5)

numDic = {1 : 1, 2 : 1, 3 : 1}

k = 3

nums = [1, 2, 3, 2, 2, 3, 3]

 

(i = 6)    # numDic에 이미 3이 존재함

 

 

오늘 문제는 생각하는데 조금 걸리긴 했지만 코드가 꽤나 예쁘게 나와서 기분이 조쿤요.

설명도 깔끔하게 적은 거 같아서 마음에 드는 포스트입니다. 모두들 화이팅 합시다!

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)