LeetCode 27 Remove Element

nayu1105·2023년 8월 23일

leetcode 알고리즘

LeetCode

목록 보기

2/28

LeetCode 27 Remove Element 풀러가기

문제

int 배열 nums에서 val의 값 삭제한다.

int 배열에서 val이 아닌 갯수, k를 리턴하면 된다.

nums의 0번 인덱스부터 k-1번 까지는 nums에서 val을 삭제한 배열을 저장한다.

nums의 크기나 k-1번 이후의 nums들은 중요하지 않다.

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

문제에서 정답 체크 기준을 보면 sort(nums,0,k)를 해서 비교하기 때문에 상관이 없나보다.

문제 분석

첫번째 시도 (소요 시간 6분)

nums의 0번 부터 k-1번에 val이 아닌 값들로 채워야 하니, 맨 뒤 값이 val과 같지 않다면 start 인덱스에 두고, start인덱스를 +1 하여 갱신하는 전략을 짰다.

end인덱스가 val과 같다면 end--를하고, 다르다면 start인덱스 값과 swap을 하고, start++을 하였다.

코드

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

        while(start<=end){
            if(nums[end] != val){
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++;
                answer++;
            }else end--;
        }
        return answer;
    }
}

결과 : 성공

Runtime

Memory

시간은 괜찮았는데 메모리 효율이 좋지는 못했다. 아마 변수를 많이 써서 인 것 같았다.

두번째 시도 (소요 시간 2분)

메모리를 줄이기 위해서, 변수를 줄이기로 했다.
생각해보니 nums배열의 k번 부터는 중요하지 않다고 했으니, swap할 필요가 없고, 그냥 무조건 앞부분 index부터 채워나가기로 했다.

for문으로 nums을 전체 순회하며 맨 앞부터 val이 아니면 채워넣도록 만들었다.

코드

class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        int count = 0;

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

결과 : 성공

Runtime

Memory

시간은 그대로이고, 메모리는 0.2MB 정도 줄였다.

지역변수를 줄여서인 듯 했다.

세번째 시도

리턴해주는 count 값을 index로 계산할 수 있는 방법을 생각해보았다.
그러다가 이전의 코드에서 결국 index 변수가 nums배열에서 val이 아닌 갯수 임을 깨달았다.

또한, 학부생일 때, index++ 계산이 index = index +1 또는 index+=1보다 효율이 좋지 못하다는 것이 기억나서 코드를 변경해보았다.

코드

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