[1주차] 80. Remove Duplicates from Sorted Array II

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

Remove Duplicates from Sorted Array II - LeetCode

---

📝 문제

오름차순으로 정렬된 nums 배열에서 연속된 동일한 값의 원소를 두 개 까지만 남기고 삭제, 그 외의 원소의 순서는 유지하라.

그 후, 남은 원소의 개수를 리턴하라.

 

 

 

🎈 풀이

다중분기문을 이용해 해결하였다. 이 방법을 이용하면 O(n) 시간에 문제를 해결 할 수 있다.

fun removeDuplicates(nums: IntArray): Int {
    var dup = false
    var idx = 0
    var prev = -1
    for (i in nums.indices) {
        if (dup && prev == nums[i]) {
            // 세 번 이상 중복상태
            // Do nothing
        } else {
            nums[idx++] = nums[i]
            //중복이 아니면 앞으로 원소를 당김
            if (dup) {
                //두 번 중복상태이나 현재는 중복이 아님
                dup = false
            } else if (prev == nums[i]) {
                // 중복상태가 아니고 이전 원소와 값이 같음
                dup = true
            } else {
                // 중복상태가 아니고 이전 원소와 값이 같지도 않음
                // Do nothing
            }
        }
        prev = nums[i]
    }

    return nums.size - (nums.size - idx)
}

• dup 변수는 현재의 중복 상태를 나타낸다. 기본값은 false 이며 이전 원소와 다음 원소가 같으면 true로 세팅된다.
• prev는 이전 원소의 값을 저장한다.
• idx 는 원소를 앞으로 당길 위치를 나타낸다.

 

prev 원소를 추가하지 않고 nums[i-1] 으로 접근하는것을 고려하였으나, 추가로 세팅할 것이 많아진다.

nums 의 길이가 3 이상일 경우, dup = nums[0] == nums[1] 이 되고, 그 이외는 false로 세팅하여야 한다.

또한 리턴값에 idx를 이용하고 있기 때문에 추가로 분기가 필요하다.

따라서 코드 가독성을 위해 prev 변수를 사용하였다.

 

6행: 현재 dup 상태이면서, 이전 원소와 다음 원소가 같다. 즉, 3번 이상 같은 원소가 나온 상태를 의미한다. 유일하게 원소를 앞으로 당기지 않는 조건이다.

12행: i-2 원소와 i-1 원소는 같아 중복상태이나 i 원소는 같지 않은 상태이다. 중복이 끝났으므로 dup를 false로 세팅한다.

15행: 중복상태가 아니었으나 i-1 원소와 과 i원소가 같아 중복상태로 돌입한다.

 

직관적으로 분기문을 작성하여 Do nothing 부분이 많아졌다. 이를 정리하면

for (i in nums.indices) {
    if (!dup || prev != nums[i]) {
        nums[idx++] = nums[i]
        if (dup) {
            dup = false
        } else if (prev == nums[i]) {
            dup = true
        }
    }
    prev = nums[i]
}

으로 요약가능하다.

 

📈 타 솔루션 참고

public int removeDuplicates(int[] nums) {
    if (nums.length <= 2) {
        return nums.length;
    }

    int index = 2;

    for (int i = 2; i < nums.length; i++) {
        if (nums[i] != nums[index - 2]) {
            nums[index] = nums[i];
            index++;
        }
    }

    return index;
}

방식은 동일하나 훨씬 더 간단하게 해결하였다...

일반적으로 두 단계 전의 원소를 비교하는 것 만으로는 3연속 같은 원소임을 판별할 수 없다. [1, 2, 1] 같은 경우가 있기 때문이다. 하지만 원소를 앞으로 당기는 조건은, "3연속이 아닐 때" 이다. 따라서 3연속이 아니면 현재원소와 두 단계 전의 원소는 같지 않다 라는 명제가 참이 된다.

 

그리고 idx가 원소를 삽입할 위치 (앞으로 당길 위치) 를 나타내므로 길이는 idx가 된다. 너무 복잡하게 생각했다.

 

PS를 하면서 매번 느끼지만 한 번 생각이 고정되면 다른 방식으로 생각하는게 정말 어려운 것 같다.