[코딩/LeetCode150-(2)] Remove Element (27)

 

 

 

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python3을 사용합니다.

 

 

 

난이도: EASY

키워드: Array, Two-Pointers

 

 

 

문제

 

문제 원문: https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150

 

정수 배열 nums와 정수 val 이 주어졌을 때 nums 내에 val 값을 in-place 형태로 제거해라. 이 때 요소 (elements)들의 순서는 바뀔 수 있다. 그리고 이렇게 업데이트 된 nums 내의 element의 수를 반환하라.

참고로 in-place 제거 시에 val 값과 같지 않은 elements들의 개수 k와 nums의 배열 길이가 같지 않을 수 있다. 채점시에는 k 이후의 값들에 대해서는 무시된다.
해당 알고리즘에서는 k 값을 함께 반환해주어야 한다.

 

문제 풀이 (Runtime: Beats 38.18 % of users with Python3, Memory Beats 94.06%)

 

문제를 보자마자 Two pointer trick으로 쉽게 풀 수 있는 easy 문제라고 생각했다. inplace형태로 array를 순환하되 val값과 같은 경우 뛰어넘고 다른 값을 넣어줘야한다. 다양한 방법들이 있겠지만, 나는 값을 inplace하는 커서에 해당하는 left 그리고 값을 조회하는 커서에 해당하는  right를 두어 추가적인 memory 없이 본 문제를 해결하도록 문제를 해결했다.

 

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:

        left, right = 0, 0

        while right < len(nums):
            if nums[right] == val:
                right += 1
                continue
            nums[left] = nums[right]
            left += 1
            right += 1
        
        return left

 

left는 현재 목적에 맞추어 in-place되고있는 cursor이고, right는 전체 array를 조회하기위한 cursor이다. 따라서 right cursor가 val 값과 같은 경우에는 left위치에 작성하지 않고, 그렇지 않은 경우에는  left 위치에 옮겨써준다. 이렇게 right 커서가 전체 array를 순회할때까지 가게되면 최종적으로 left의 위치가 in-place로 업데이트된 array의 길이가 된다.

 

복잡도

 

N을 nums의 길이라고했을 때, 시간 복잡도 O(N), 공간 복잡도 O(N)

 

 

📚 LeetCode 75 / Code Signal 풀이 보러가기