[Leetcode Top Interview 150] 27. Remove Element

난이도 : easy 

문제링크

• val 과 일치하는 원소들을 nums 에서 지워라 (in-place)
• nums의 갯수를 리턴하라
• 지우고 남은 nums는 모두 앞으로 당겨져야 함
  • 당겨진 원소들의 순서는 중요하지 않음
  • 지워진 원소들은 '_'로 표기

input

• int[] nums
  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
• int val
  • 0 <= val <= 100

 

1. 접근법

• 배열 + in-place 문제 : 탐색하면서 조작을 해야된다 (formula 도출하기)
• 남아있는 원소들이 앞으로 당겨져야 하니까 뒤에서부터 탐색
  • 현재 방문한 요소가 val과 같지 않다면, offset 하나씩 올려주기
  • 현재 방문한 요소가 val과 같다면, '_'로 변경 + 쌓인 offset만큼 뒤로 밀기

 

2. 의사코드

while(뒤에서부터 인덱스로 방문 탐색) {
   if (방문한 요소가 val과 같지 않음) {
      count 갯수 하나 증가
      
   }

   if (방문한 요소가 val과 같음) {
      방문한 요소값을 '_'로 변경
      offset값 만큼 뒤로 밀기
   } 
   
   다음에 방문할 인덱스 수 하나 감소
}

! 생각해보니 뒤로 밀게되면 반복문을 돌아야 하므로 O(n) 곱만큼 늘어난다

뒤로 보내져서 앞에 남겨진 원소들이 쌓이는 것이 중요하므로

(현재 노드의 인덱스)와 (마지막 인덱스 - offset) 값인 인덱스와 스왑해도 맨 뒤로 미는 효과가 있다

 

3. 구현 코드

class Solution {
    public int removeElement(int[] nums, int val) {
        int length = nums.length;        
        int searchIdx = length - 1;
        int offset = 0;

        while (searchIdx >= 0) {
            int curNum = nums[searchIdx];
            
            if (curNum == val) {                 
                nums[searchIdx] = '_';
                                                
                int sourceIdx = searchIdx;
                int targetIdx = length-1-offset;                                
                nums[sourceIdx] = nums[targetIdx];

                int source = nums[sourceIdx];
                nums[targetIdx] = source;
                
                offset++;
            }

            searchIdx--;
        }

        return length - offset;
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - n개 원소까지 반복하므로
• 공간복잡도 : O(n) - worst case 매번 스왑이 이루어지면 지역변수 선언됨

5. 개선점

• 공간복잡도 개선 : 상위 블록에 변수를 선언하고 변수값을 바꾸는 방식으로 바꾸면 메모리 사용량이 줄어들 것 같다

 

6. 회고

class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[index++] = nums[i];
            }
        }
        
        return index;
    }
}

(출처 : https://bcp0109.tistory.com/172)

다른 분의 풀이를 보았다.

val과 일치하지 않으면 출력 대상이니, 첫번째 인덱스부터 값을 넣어주면 되는 간단한 문제였다

정말 간단하다 (대단)

 

지난번 문제에서 뒤로 접근하는 것을 기억하려고 했고 그렇게 풀었다

왜 뒤로 접근하려 했는지 고민이 부족하고 가지고있는 수가 적어서 그런 것 같다.

연습량을 늘려야겠다..