[LeetCode] 27. Remove Element

Remove Element - LeetCode

 

array nums와 val이 주어지면 int형 array 안에val과 같은 값이 있으면 제거하고

array에 남은 값들만 반환하면 됩니다.

 

이때 남은 값든의 숫자를 반환하고 주어진 array의 0~반환한 숫자까지의 범위안에

삭제되지 않은 값들이 존재해야 합니다

남겨진 array에 순서는 상관없습니다.

 

문제 접근법

 저의 풀이법은 반환할 cnt값을 array사이즈로 할당하고

array를 loop순회 하면서 val과 같은값이 있다면 cnt를 빼주는 것입니다.

그리고 같지 않다면 temp 배열에 값을 넣어주었습니다.

 

temp 배열에는 val과 같지 않은 값이 들어가고

cnt에는 val과 같은 숫자만큼 빼주는 로직입니다.

 

수도코드

cnt = array.length
for (~array.length)
	if (array[i] == val)
    	cnt--
    else
    	temp[pointer] = array[i]
        
return cnt

 정답 코드

public int removeElement(int[] nums, int val) {
        int[] temp = new int[nums.length];

        int cnt = nums.length;
        int tmpPointer = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                cnt--;
            } else {
                temp[tmpPointer++] = nums[i];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
        return cnt;
    }

 

시간복잡도

시간복잡도는 for문을 nums.length만큼 반복하고 있으니

O(n)입니다.

 

공간복잡도

주어진 배열 이외에 temp 배열을 하나 더 만들었습니다.

O(n2)의 공간복잡도가 필요합니다.

 

하지만, 문제에서 보면 새로운 배열을 할당하지 말라는 조건이 있습니다.

이 조건을 해결하기위해 다른사람들의 풀이를 참고하였습니다.

다른사람의 풀이

투포인터를 사용하여 새로운 배열을 할당하지 않고 해결한 코드를 참고하였습니다.

 

현재 확인하는 nums의 데이터와 val이 일치하지 않다면
count의 위치와 i의 위치에 있는 데이터를 교환하는 방식입니다.

 

count는 val과 같은 데이터를 바라보는 pointer입니다.

데이터가 같다면 count는 가만히 있고 i의 값만 증가하기 때문에  이후에 다른값이 나온다면

count와 i에 위치한 데이터를 교환하여 val과 같은값의 데이터를 뒤쪽으로 보냅니다.

 

그리고 count를 리턴하게되면 자연스럽게 다른값들만 포함한 범위를 반환하게 되는것입니다.

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

 

시간복잡도

시간복잡도는 for문을 nums.length만큼 반복하고 있으니

O(n)입니다.

 

공간복잡도

주어진 배열만 사용하고 있습니다.

O(n)의 공간복잡도가 필요합니다.

 

 

느낀점

투 포인터를 활용하면 탐색을 할때 loop를 활용해 탐색하는것보다 훨씬 효율적이라는 것을

다시한번 깨닫게 되었습니다.

 

각 포인터마다 어떤 역할을 할당해야할지 고민해보며 투포인터를 사용해야 겠습니다.

 

참고

Replacing the position of Array - Remove Element - LeetCode