LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 숫자가 든 배열 nums, 타겟 숫자 val
2. output: nums에서 val을 모두 제거하였을때 길이 k, 제거 후 nums
3. 리턴한 nums에서 idx=k 이후의 원소는 상관X
4. nums 앞에서 부터 k개 까지의 원소의 순서 상관X
5. 공간 복잡도 O(1), in-place로 풀 것
   • 0 <= nums.length <= 100
   • 0 <= nums[i] <= 50
   • 0 <= val <= 100

Idea

idx=k 이후의 원소는 보지 않고, val 제거후 남은 원소들의 순서도 상관없기 때문에, nums의 앞에서 부터 val인 원소를 nums의 뒤에서 부터 val이 아닌 원소와 swap해주면 된다.

→ 사실 문제 조건이 in-place 배열 조작이기 때문에 무조건 swap

Solution

1. Swap

   • 왼쪽 커서 cursor → val을 찾을 때까지 오른쪽으로 이동
   • 오른쪽 커서 changeCursor → val이 아닌 값을 찾을 때까지 왼쪽으로 이동
   • cursor값이 val이고 changeCursor값이 val이 아니면 swap

   class Solution {
       fun removeElement(nums: IntArray, `val`: Int): Int {
           var cursor = 0
           var changeCursor = nums.size - 1
           while (cursor <= changeCursor) {
                   if (nums[cursor] != `val`) {
                       cursor++
                       continue
                   }
                   if (nums[changeCursor] == `val`) {
                   changeCursor--
                   continue
               }
               nums[cursor] = nums[changeCursor].also{nums[changeCursor] = nums[cursor]}
           }
           return cursor
       }
   }
   

   시간 복잡도: 문자열 순회 = n

   

Point