Remove Element

Remove Element

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

문제요약

• input
  • nums: 정수 배열
  • val: 정수
• nums 배열 제자리에서 val과 일치하는 모든 값을 제거

풀이

• nums 배열 안에 있는 요소 중 val과 일치하는 모든 값을 제거한다.
  • nums에 val과 일치하는 원소 개수 n를 센다.
  • n번만큼 반복하여 nums에서 val을 삭제한다.
• output으로 삭제하고 난후 nums의 길이를 리턴한다.

수도코드

def solution(nums, val):
	n = count(nums, val)
    
    while n:
    	nums.remove(val)
        n -= 1
        
    return nums.size

Solution(runtime: 40ms)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = nums.count(val) # k

        while n:
            nums.remove(val)
            n -= 1

        return len(nums)

nums의 최대 길이는 100으로 이 풀이의 시간복잡도는 O(kn)이다. k번 돌면서 nums에 저장된 원소를 제거하는 과정에서 O(n)이 발생하게 된다.(중간 삭제의 경우, 원소를 앞당겨야 하기 때문)