리트코드 - 26. Remove Duplicates from Sorted Array

리트코드 - 26. Remove Duplicates from Sorted Array

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

 

문제 설명

정렬된 비내림차순으로 주어진 정수 배열 nums에서 중복된 요소를 제거하되, 각 고유한 요소는 한 번씩만 나타나도록 제거하세요. 고유한 요소들의 상대적인 순서는 유지되어야 합니다. 그리고 고유한 요소의 수를 반환하세요.

nums의 고유한 요소의 수를 k라고 가정할 때, 다음 작업을 수행해야 합니다:

1. 배열 nums를 수정하여 처음 k개의 요소가 nums에 고유한 순서대로 나타나도록 변경하세요. 나머지 nums의 요소는 중요하지 않습니다. 또한 nums의 크기 역시 중요하지 않습니다.
2. k를 반환하세요.

의사코드

커스텀 인덱스를 0으로 저장 중복여부를 false로 저장 반복문 시작     배열의 커스텀 인덱스 값을 저장     만약 저장 값과 같은 값이 있고 중복여부가 false라면         중복여부를 true로 변경         배열의 커스텀 인덱스에 값을 저장     만약 값이 다르다면         중복여부를 false로 변경         배열의 커스텀 인덱스 + 1 번째에 값 저장 반복문 종료 k값에 커스텀 인덱스 + 1 값 대입

풀이코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        int idx = 0;
        int size = nums.length;
        boolean isDuplicated = false;

        for (int i = 1; i < size; i++) {
            int num = nums[idx];
            if (nums[i] == num && !isDuplicated) {
                isDuplicated = true;
                nums[idx] = num;

            } else if (nums[i] != num) {
                isDuplicated = false;
                nums[++idx] = nums[i];
            }
        }
        return k = idx + 1;
    }
}

코드설명

중복을 판별하는 isDuplicated 값을 만들어 배열을 순회하면서 만족하는 값을 0번 인덱스부터 추가한다.

우선 배열의 0번째 값을 비교할 기준값으로 num에 대입하고, 배열의 i = 1번째 값부터 비교를 시작한다.

 

중복값이 나오면 isDuplicated 가 true가 되고 인덱스에 해당 값을 넣는다.

다음 순회에서 중복값이 나와도, isDuplicated가 true이므로 지나간다.

중복이 아닌 값이 나오면 isDuplicated 를 false로 바꾸고, 다음 인덱스에 해당 배열값을 넣는다.

 

넣은 인덱스 값은 고유값들만 넣은 인덱스이므로 +1을 하여 k를 반환한다.(인덱스는 0부터 시작하므로)

 

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

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

먼저 가장 먼저 드는 생각 두가지는 set으로 만든다음 다시 배열로 변환하기, 스트림으로 중복 제거하기 였다.

LinkedHashSet으로 배열 변환하기

import java.util.*;

class Solution {
    public int removeDuplicates(int[] nums) {
        LinkedHashSet<Integer> set = new LinkedHashSet<>();

        for (int num : nums) {
            set.add(num);
        }
        int k = 0;

        Iterator<Integer> iterator = set.iterator();
        while(iterator.hasNext()) {
            nums[k] = iterator.next();
            k++;
        }
        return k;
    }
}

스트림으로 중복 제거하기

class Solution {
    public int removeDuplicates(int[] nums) {
        int[] deleteDuplicatedNums = Arrays.stream(nums)
                                                .distinct()
                                                .toArray();
        int k = deleteDuplicatedNums.length;

        for (int i = 0; i < k; i++) {
            nums[i] = deleteDuplicatedNums[i];
        }
        return k;
    }
}

그래서 우선 직접 구현하는 방법으로 먼저 해결해보고, 나중에 나머지 방법으로 구현해보았다.

세개를 모두 돌려보니 메모리가 차지하는 비율은 비슷했지만, 런타임은 1ms / 3ms / 9ms 로 차이가 났다.

static 메소드 대신 직접 로직을 구현한 것이 가장 속도는 빨랐다.

하지만 이것은 테스트코드를 통과한 것일뿐 생각하지 못한 예외가 더 있을수도 있다.

 

리트코드가 좋은 점이 런타임별, 메모리별로 빠른 걸 구현한 코드들을 즉각적으로 볼 수 있다는 점이 좋은 것 같다.

이번주는 직접 구현하는데 목표가 있기 때문에 우선은 만족한다!

 

다른 풀이

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

배열의 0번째 값은 중복이든 아니든 입력이 보장되는 값이기 때문에 1번부터 순회하고 있다.

내가 생각한 방법과 비슷하지만 비교할 기준 값을 지정하지 않고 곧바로 비교하다보니 코드가 명쾌하다.

 

그냥 공식처럼 외워도 좋을것 같다는 생각이다. 

 

정리

배열에 중복을 제거하는 방법은 여러가지가 있지만, 간단하게도 가능하다.

의사코드를 조금 더 심도있게 고민해서 생각해보자.