Remove Element

Nine-JH·2023년 8월 25일
0

leetCode

목록 보기
1/5

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

문제 정리

배열에서 제시된 수와 같은 값을 가지는 원소를 제거하여 총 몇개의 원소가 남았는지를 구하는 문제입니다. 몇가지를 주의해야 합니다.

  • 제거된 배열의 크기는 원래 nums의 크기와 같다.
  • 제거되어 비어버린 원소는 뒤로, 값이 있는 원소들은 앞으로 모여있어야 한다.
  • nums = {1, 2, 3, 3, 2, 1}, val = 2 라면 최종적으로
    nums = {1, _, 3, 3, _, 1} 이 아니라...
    nums = {1, 3, 3, 1, _, _} 이 되어야 함.


풀이 시작

Main Idea

  • val와 탐색하는 원소가 다르면 입력을 한다.
  • 이때 입력될 최신 Index 위치를 알고 있어야 한다.


1st. 시작 (탐색 index = 0, 입력 index = 0)

1은 val와 다르기 때문에 두가지 과정을 진행합니다.

  • 입력 index에 탐색한 index element 덮어 씌우기. (같은 값이라 영향 X)
  • 탐색과 입력 모두 +1 이동 하기.

2nd. val과 같은 값 발견! (탐색 index = 1, 입력 index = 1)

이번에는 val와 같은 값이군요! 다음 과정을 진행합니다.

  • 그럼 탐색 index만 +1 이동하고 입력 index는 이동하지 않습니다.
  • 이는 후에 val와 다른 값이 나올때 덮어쓰기 위함입니다.

3rd. val와 다른 값 (탐색 index = 2, 입력 index = 1)

3은 val와 다른 값입니다. 그러므로 두 과정을 진행합니다.

  • 입력 index에 탐색한 index element 덮어 씌우기. (2 -> 3)
  • 탐색 입력 모두 +1 이동하기

4th. val와 다른 값 (탐색 index = 3, 입력 index = 2)

3은 역시 val와 다른 값이기 때문에 두 과정을 진행하면 됩니다.

5th. val와 같은 값 (탐색 index = 4, 입력 index = 3)

이번에는 같은 값이군요. 탐색 index만 +1 이동하고 입력 index는 이동하지 않습니다.

6th. val와 다른 값 (탐색 index = 5, 입력 index = 3)

입력 index에 탐색한 값을 덮어 씌우면 됩니다.

7th. 탐색 종료 (탐색 index = 6, 입력 index = 4)

탐색 index가 배열의 끝까지 도달했기 때문에 탐색을 종료합니다.



코드

class Solution {
    public int removeElement(int[] nums, int val) {
        int inputIndex = 0;
        int length = nums.length;

        for (int searchIndex = 0; searchIndex < length; searchIndex++) {
            if (nums[searchIndex] != val) {           // 값이 다르면...
                nums[inputIndex] = nums[searchIndex]; // 덮어 씌우기
                inputIndex++;                         // 입력 index +1
            }
        }
        return inputIndex;
    }
}

0개의 댓글