[ Top Interview 150 ] 27. Remove Element

문제

• 27. Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

• nums에 있는 val가 동일한 값을 앞부분에서 제거한다.
• nums에 val과 값이 다르면서 기존에 있었던 값은 nums의 앞부분에 있어야 한다.
  • 순서는 고려하지 않아도 된다.
• 변경되지 않은 원소의 개수를 return 한다.

문제 풀이 전략

• 초기에 앞 원소는 배열에 맨 처음에 있는 원소, 뒤 원소는 배열에 맨 뒤에 있는 원소로 설정한다.

• 앞 원소와 뒤 원소가 서로 지나칠 때까지 반복한다

  • 앞 원소가 val과 같지 않으면 앞 원소을 다음 원소로 설정한다.

  • 앞 원소가 val과 같을 때

    • 뒤 원소가 val과 같지 않으면 뒤 원소를 앞 원소 자리에 넣어주고 뒤 원소 자리에는 val가 다른 아무 값을 넣어준다. 그리고 앞 원소와 뒤 원소를 각각 다음에 있는 원소로 설정한다.

    • 뒤 원소가 val과 같으면 뒤 원소를 다음 원소로 설정한다.

• 전체 원소의 개수와 원소 바뀐 횟수를 빼서 결과값을 반환한다.

1차 작성

class Solution {

    public int removeElement(int[] nums, int val) {
        int frontIndex = 0; int behindIndex = nums.length - 1;
        int trashValue = val + 1;
        int trashCount = 0;

        while (frontIndex <= behindIndex) {
            if (nums[frontIndex] != val) {
                frontIndex++;
                continue;
            }

            if (nums[behindIndex] != val) {
                nums[frontIndex] = nums[behindIndex];
                nums[behindIndex] = trashValue;
                frontIndex++;
            }
            behindIndex--;
            trashCount++;
        }

        return nums.length - trashCount;
    }
}

모범 답안 찾아보기

• 모범 답안 전략

  • 선별이 완료된 원소의 위치를 가리키는 i를 설정
  • nums를 순회하면서 val과 다른 nums의 원소를 i번째와 자리를 바꿈

• 모범 답안

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

• 내가 생각하지 못한 부분

  • 무조건 조건에 맞지 않는 원소를 제거해야 한다고 생각했다.
  • 최소한의 교체만이 좋은 퍼포먼스를 낸다고 생각했던 것 같다.