[leetcode][파이썬]Remove Duplicates from Sorted Array #007

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

 

 

 

---

 

 

 

오늘풀어본 문제는 " Remove Duplicates from Sorted Array" 이다.

문제에서 요구하는 것은 오름차순으로 정렬되고 정수로 이뤄진 배열이 주어진다. 주어진 배열에서 중복된 요소를 제거하여 각 고유한 요소가 한 번만 나타내도록 해야한다. 단, in-place 방식으로 구현해야 한다.

 

 

 

풀이 #1 - Two Pointer 알고리즘

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

        for fast in range(len(nums)):
            if nums[slow] < nums[fast]: 
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

 

in-place 방식으로 구현이란 조건을 보기 전에 stack을 활용해 풀면 쉽게 풀리겠다고 생각했다.

in-place 방식 의미는 배열의 추가 공간을 사용하지 않는다는 의미이기도 하다.

유니크한 값을 남겨야 되는 상황이므로 중복된 값이 달라지는 요소의 인덱스를 활용해야 겠다고 생각했다.

동시에, 유니크한 자리 위치도 기억하고 있어야 했기 때문에 two pointer 기법이 적절하다고 판단했다.

 

 

풀이 순서

1. 주어진 배열을 가장 처음 위치한 값부터 순환하기 위해, slow = 0와 같이 초기화

2. 주어진 배열 길이만큼 순환하는 반복문을 선언한다.

  - 반복문의 인덱스는 fast라고 함

  - slow와 fast는 각 포인터로 인덱스 역할

  2-1. slow 위치값과 fast 위치값을 비교해, fast 위치값이 클 경우, 유니크한 값이 들어가는 위치라고 볼 수 있음

    - slow에 +1를 하여 바꿔줄 위치를 잡아줌

    - slow 위치에 fast 위치값을 할당하여 유니크 값을 할당

3. slow가 유니크 값을 할당할 때마다 이동했으므로, 유니크값의 갯수라고도 볼 수 있으므로 slow + 1를 반환

 

 

 

알게된 점

- in-place 방식으로 구현해야 할 경우, two pointer 사용하는 법에 대해 알게 되었다.