리트코드 - 27. Remove Element

리트코드 - 27. Remove Element

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

 

문제 설명

주어진 정수 배열 nums와 정수 val이 있습니다. nums 배열에서 모든 val 값을 제거하고, 원소의 순서는 변경될 수 있습니다. 그런 다음 nums 배열 내에서 val과 다른 요소의 개수를 반환해야 합니다.

nums 배열 내에서 val과 다른 요소의 개수를 k라고 가정해보겠습니다. 문제를 풀기 위해서는 다음과 같은 단계를 수행해야 합니다:

1. nums 배열을 변경하여 첫 번째 k개의 요소가 val과 다른 요소를 가지도록 합니다. 나머지 요소들은 중요하지 않으며, nums 배열의 크기도 중요하지 않습니다.
2. k를 반환합니다.

의사코드

반복문 시작 (nums1 배열 처음부터 끝)     배열 값과 val 값이 다르면        k값 1 추가     같으면        마지막 인덱스의 배열값과 현재 배열값 교체        마지막 인덱스 값 -1 감소        배열 인덱스 -1 감소     만약 현재 인덱스가 마지막 인덱스랑 같아지면        반복문 종료 반복문 종료

풀이코드

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

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                k++;
            } else {
                swap(nums, i, lastIndex);
                nums[lastIndex] = -1;
                lastIndex--;
                i--;
            }

            if (i == lastIndex) {
                break;
            }

        }
        return k;
    }

    static void swap(int[] a, int idx1, int idx2) {
        int temp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temp;
    }
}

코드설명

nums 배열을 순회하여 그 값이 val 값이랑 일치하지 않으면 k값을 추가하고,

만약 val값이랑 같다면 두 값을 swap 메소드를 이용해 값을 바꾸고 마지막 인덱스에 -1을 추가하는 로직이다.

 

또한 nums배열을 계속 순회하는게 아니라 두 값의 교체가 일어나면 다시 앞의 값을 조회하기 위해 i에도 -1 감소가 추가되었다.

 

시간복잡도 - O(n) (최대 n크기만큼의 배열을 순회함)

공간복잡도 - O(1) (배열 하나만 사용)

문제를 풀며 어려웠던 점과 배운 점

1. 의사코드의 효율성

첫번째 문제를 풀때는 문제가 간단하다고 생각되어 의사코드를 생략했는데 상당히 고생을 했다.

그래서 이번에는 의사코드를 먼저 만들고 코딩을 하기 시작했다.

의사코드로 짜다보니 내가 생각한 부분으로만 돌아가지 않는 예외처리 해야 될 부분이 많이 보였다.

그래서 우선 기본 의사코드를 짜고 코드를 돌려보고, 오류가 나면 계속 수정을 했다.

코드 자체적으로 볼 때는 뭔가 실수를 저지르면 내가 짠 코드임에도 내가 헷갈렸는데 의사코드로 보니 잘못된 로직을 빠르게 파악할 수 있었다.

 

2.call by value

처음에 swap 메소드를 만들었는데, 매개변수를 int a와 int b만 가지고 하다보니 call by value가 일어나 실제 값이 바뀌지 않았다.

자바에서는 변수의 전달방식이 call by value이지만, 원시타입인 byte,short,int,long,float,double,char,boolean 만 해당이된다.

String을 비롯한 레퍼런스 타입은 주소값이 저장이 되기 때문에 복사가 되더라도 원본이 바뀔 수 있다.

 

하여 직접 배열 값을 파라미터에 전달하여 값을 변경하였다.

 

3. 다른 풀이

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];
                index++;
            }
        }
        return index;
    }
}

다른 풀이를 봤는데 무척이나 심플하다. 여기서 내가 문제를 잘못 읽었다는 것을 파악했다.

조건 1에보면 nums 배열을 변경하여 첫 번째 k개의 요소가 val과 다른 요소를 가지도록 합니다. 라는 문구가 있는데,

nums 배열에 있는 어떤 요소든 k값과 같다면 다른 값으로 치환해야 한다고 해석했다. 

 

어짜피 k개의 요소만 잘라서 필요하므로 더 단순해질 수 있는 코드였다.

 

정리

의사코드를 열심히 적으면 예외처리를 만날 일이 적어지고, 예외처리 할 때도 좀 더 직관적으로 가능하다.

자바에서 지역변수 사용에 주의할 것. call by value가 될 수 있다.

문제를 제대로 읽어서 필요없는 로직을 구현하는 일은 없도록 하자.