[Dart] LeetCode 27. Remove Element

1. 문제

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

 

 

2. 요구사항

1) 배열 nums에서 val과 같은 값을 제거합니다.
2) 배열의 순서는 변경될 수 있습니다.
3) val이 아닌 원소들로 이루어진 새로운 길이 k를 반환합니다.
4) nums의 첫 k개 요소는 val이 아닌 값으로 채워져 있어야 합니다.
5) 배열의 나머지 요소는 중요하지 않습니다. (어떤 값이 남아도 괜찮음)

 

 

3. 핵심 아이디어

1) Two Pointer

두 개의 포인터를 사용하여 값을 이동합니다.

 

첫 번째 포인터는 배열을 순회하며, 현재 검사중인 요소를 가리킵니다.

두 번째 포인터는 val이 아닌 값을 저장할 위치를 가리킵니다.

 

즉, 두 개의 포인터로 배열을 순회하며,

val과 해당 요소의 값이 다르다면, 저장 포인터가 있는 곳에 해당 요소의 값을 넣습니다.

그리고 count에 1을 더한 후, 저장 포인터도 1을 더해줍니다.

 

그림으로 표현하면 다음과 같습니다.

 

nums의 0번째 요소는 3입니다.

우리가 찾아야 할 val값과 같기 때문에 순회 포인터는 다음 요소로 넘어갑니다.

하지만, 저장 포인터는 가리키는 곳에 값을 저장하지 않았기에 저장 포인터는 두 번째 순회에도 같은 곳을 가리킵니다.

 

두 번째 순회입니다. 

순회 포인터는 1번째 요소인 2를 가리킵니다.

2는 val값인 3과 다르기 때문에 저장 포인터에 2를 넣은 후,

count값과 저장 포인터 값을 1씩 증가시킵니다.

세 번째 순회입니다. 

nums의 2번째 요소인 2는 val값과 다르기 때문에 저장 포인터에 2를 저장한 후,

count값과 저장 포인터를 1씩 증가합니다.

네 번째 순회입니다.

nums의 세번째 요소인 3은 val값과 같기 때문에 다음 순회로 넘어갑니다.

 

nums의 길이가 4이기 때문에 순회는 끝났습니다.

문제에서 요구하는 것은 count의 값이기 때문에 바뀌지 않은 nums의 뒷부분은 신경쓰지 않아도 됩니다.

 

 

2) Two Pointer 코드

 

class Solution {
  int removeElement(List<int> nums, int val) {
    int count = 0; 							// 저장 위치 포인터

    for (int i = 0; i < nums.length; i++) { // 순회 포인터
      if (nums[i] != val) {
        nums[count] = nums[i]; 				// val이 아니면 저장 위치에 해당 요소 대입
        count++; 							// 저장 위치 증가
      }
    }
    return count; 							// val이 아닌 요소들의 개수 반환
  }
}

 

시간 복잡도 : O(n)

- 입력 크기에 따라 실행 시간이 선형적으로 증가

- 리스트를 한 번 순회

 

공간 복잡도 : O(1)

- 추가적인 리스트를 사용하지 않음

 

 

3) removeWhere를 이용한 원소 제거

 

두 개의 포인터를 활용하는 대신 removeWhere를 사용하여 더 간단하게 코드를 작성할 수 있습니다.

 

removeWhere는 리스트에서 조건을 만족하는 요소를 모두 삭제합니다.

 

val값과 해당 요소의 값이 일치하면 해당 요소를 삭제하는 방식으로 진행됩니다.0

 

 

4) removeWhere를 이용한 코드

class Solution {
  int removeElement(List<int> nums, int val) {
  	nums.removeWhere((value) => value == val);	// value값과 val값이 같을 경우, 해당 요소 삭제
  	return nums.length;							// 삭제 후, 남은 nums의 길이값 반환
  }
}

 

시간 복잡도 : O(n)

- removeWhere()는 내부적으로 각 요소를 순회하며 검사하므로 입력 값 nums의 길이에 따라 달라짐

 

공간 복잡도 : O(1)

- 추가적인 리스트를 사용하지 않음