5/9 화 [LeetCode #26] 순서를 유지하여 배열에서 중복 숫자 제거하기 TIL

[LeetCode] 26. Remove Duplicates from Sorted Array

문제:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.

Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

1 <= nums.length <= 3 * 104

100 <= nums[i] <= 100

nums is sorted in non-decreasing order.

나의 풀이:

nums를 뒤에서부터 검사하여 중복되지 않는 수면 제일 앞으로 보내기를 반복한다.


var removeDuplicates = function(nums) {

		// The way that perfectly keeps both the original size and relative order of elements after the sorting. 
    // => Iterate from back to front and bring the unique numbers to the very first position.    let uniqueCount = 0;
    for (let target = nums.length - 1; target >= uniqueCount; target--) {
        if (nums[0] !== nums[target]) {
            for (let i = target; i > 0; i--) {
                [nums[i], nums[i-1]] = [nums[i-1], nums[i]];
            }
            uniqueCount++;
            target++;
        }
    }

    return uniqueCount === 0 ? 1 : uniqueCount;
};

⇒ nums = [0,0,1,1,1,2,2,3,3,4] 같은 인풋이 주어진다고 할 때, 뒤에서부터 검사한다. 검사 대상인 target이 첫 수와 값이 같지 않으면 제일 앞으로 배치한다. 나머지는 뒤로 민다.

뒤에서부터 target을 지정하는 이유: target보다 더 뒤의 수들은 관심 밖이므로. 중복되지 않는 수를 제일 앞으로 모으는 것이 목적이므로.

두 번째 for 루프에서 뒤에서부터 iterating을 하는 이유: target을 맨앞으로 당겨오기 위하여. 만약 가장 앞의 수를 가장 뒤로 보내고 싶다면 앞에서부터 두 개씩 서로 swap 해나간다.

검사 조건이 ‘두 수가 값이 같지 않다’인 이유: 이미 오름차순으로 정렬되어 있으므로 처음 비교 때는 무조건 nums[0] ≤ nums[target]이 되고, nums[0] < nums[target]일 때 자리를 바꿔야 한다. 한 번 자리바꾸기가 진행된 이후부터는 nums[0] ≥ nums[target]이 되고, nums[0] > nums[target]일 때 자리를 바꾼다. 때문에 자리를 바꾸는 공통 조건을 nums[0] ≠ nums[target]으로 설정했다. 이는 이미 non-decreasing order로 정렬이 되어있기 때문에 가능한 설정이다. 그렇지 않았다면 첫 자리바꾸기는 for 문 밖으로 빼고, 그 이후부터를 for 문 안에서 돌면서 nums[0] > nums[target]일 때 자리를 바꾼다고 조건을 각각 지정해야 했을 것이다.

if 문 안에서 target을 증가시키는 이유: target 인덱스에 해당하는 수를 맨앞으로 배치했다면, 그 다음 검사도 다시 target 인덱스에 해당하는 수로 해야 한다. 한 칸씩 뒤로 밀렸을 것이므로. 그렇지 않으면 뒤로 밀려온 수를 건너 뛰고 검사하게 되어 구멍이 생긴다.

for 문을 target ≥ uniqueCount 까지만 도는 이유: 그렇지 않고 ≥ 0까지 돌면 무한 루프가 된다. if 문 안에 target++를 주었기 때문에 생긴 현상이다. 2개 이상의 중복되지 않는 숫자가 존재하는 경우, 맨 앞의 수들이 전부 중복되지 않는 수로 모이게 되었을 때 계속해서 if 문에 들어가게 되고, target++ 때문에 바로 이 시점의 target 인덱스가 줄어들지 않고 무한히 검사되게 된다. ‘맨 앞의 수들이 전부 중복되지 않는 순간’이 바로 target == uniqueCount가 되게 되는 순간이므로 여기까지만 검사하고 끝내주면 된다.

마지막에 uniqueCount가 0이면 1을 반환하는 이유: nums[0] ≠nums[target]의 조건을 만족해서 자리가 한 번 변경되어야 uniqueCount가 증가하기 시작하는데, [1, 1, 1, 1]같이 모든 수가 같은 경우엔 한 번도 if문에 들어가지 못하고 검사가 끝나 uniqueCount는 0으로 남게된다. 그러나 제약 조건에 nums의 길이가 1 이상이라고 했으므로 무조건 한 개의 중복되지 않는 수가 존재한다. 즉, return할 때가 되어서 uniqueCount가 0이 된 경우라면 주어진 nums 배열에 전부 같은 수가 들어있다는 뜻이고, 이 때 중복되지 않는 수의 개수는 “1개”일 수밖에 없다.

다른 풀이:

// 중복되지 않는 수로 그냥 앞에서부터 차례대로 덮어 씌워버리는 방법. 
var removeDuplicates = function(nums) {
    let i = 0;
    for (let j = 0; j < nums.length; j++) {
        if (nums[j] != nums[i]) 
            nums[++i] = nums[j];
    }
    return ++i;
};

알게된 것:

구조 분해 할당을 이용한 배열 자리 바꾸기.

두 개씩 차례로 스왑하여 맨 뒤의 수를 앞으로 보내고 싶을 땐 뒤에서부터 for 문을 돌기. 맨 앞의 수를 뒤로 보내고 싶으면 앞에서부터 for 문 돌기.

[...nums.slice(0)] = [nums[9], ...nums.slice(0, 9)] 같은 방식은 왜 안되는지 모르겠다. 분명히 같은 원리인 것 같은데… 이런 에러가 난다: Uncaught SyntaxError: Invalid destructuring assignment target

본래의 array 내에서 변환시키는(in-place) 배열 메소드: splice(), sort(), reverse(), 인덱스를 이용한 삽입/삭제.
- ↔ 새 array를 반환하는 메소드: slice(), map().

※ 위 내용은 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※

Uploaded by N2T

[LeetCode] 26. Remove Duplicates from Sorted Array

티스토리툴바