Leetcode80.RemoveDuplicatesFromSortedArrayII

소스코드

문제

• 80. RemoveDuplicatesFromSortedArrayII

풀이 (brute-force)

• 문제는 array 의 중복을 제거하는 것인데 최대 2개까지 허용
• 중복 제거된 array 의 length 를 return 하고 중복 제거 후, nums 배열을 바꿔줘야함
• 시간복잡도 O(n 제곱)
• 순회하면서 앞뒤로 비교
• 값이 같으면 2개까지 중복허용하고, 3개 이상 부터는 버림
• 값이 틀리면 nums 를 수정
• 요약 : nums 배열을 바꿔주면서 nums.length 를 구하는 것. 같으면 nums 배열 유지. 단, equalCount = 2 까지, 다르면 nums 채워넣어야 함

    /**
     * 1, 1, 1, 2, 2 ,3
     * 1 고정
     * 1, 1 eq = 2
     * 1, 1, 1 은 eq = 3 이니 skip -> 1, 1
     * 1, 1, 1, 2 ->  1, 1, 2
     * 1, 1, 1, 2, 2 -> 1, 1, 2, 2
     * 1, 1, 1, 2, 2, 3 -> 1, 1, 2, 2, 3
     */
    fun removeDuplicates(nums: IntArray): Int {
        var k = 1
        var equalCount = 1
        for (i in 1 until nums.size) {
            if (nums[i] != nums[i - 1]) {
                nums[k++] = nums[i]
                equalCount = 1
            } else {
                if (equalCount < 2) {
                    nums[k++] = nums[i]
                    equalCount++
                }
            }
        }
        return k
    }