Week 1-1. [Array / String] 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 | int arrray := 중복된 원소가 포함된 배열, | nums | ∈ [1, 3 * 10^4]
• 출력
  • k | int := nums 배열에서 의미있는 원소의 개수 (쓰레기 원소 제외)
• 조건
  • | nums[i] | ∈ [-10000, 10000]
  • nums 배열은 오름차순 정렬되어있다.

 

🔎 어떤 식으로 접근했는가?

Two Pointer 방식을 생각했다. 그리고 연속으로 중복되는 수의 개수를 카운트한다.

 

크게 바로 전 수와 같을 때와 바로 전 수와 다를 때로 나뉘는데, 

바로 전 수와 같다면 카운트를 증가하고 다를 때는 카운트를 초기화한다.

 

바로 전 수와 같을 때, 카운트가 2일 때는 저장하고 2보다 크다면 저장하지 않는다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

nums의 길이가 최대 30,000이므로 for문을 이용하여 하나씩 탐색해도 된다.

 

📝 의사 코드

lp = 1;
cnt = 1;

for (rp=1부터; nums 배열 끝까지; 1씩 증가) {
	if (이전 수와 같으면) {
    	cnt 증가
        if (cnt가 2보다 작거나 같으면) {
        	nums[lp]에 nums[rp] 대입
    		lp++
        }
    } else (이전 수와 다르면) {
    	nums[lp]에 nums[rp] 대입
    	lp++
        cnt 1로 초기화
    }
}

 

🎯 구현 코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int lp = 1;
        int cnt = 1;
        
        for (int rp = 1; rp < nums.length; rp++) {
            // 이전 수와 같으면 cnt 증가
            if (nums[rp] == nums[lp-1]) {
                cnt++;
                if (cnt <= 2) {
                    nums[lp] = nums[rp];
                    lp++;
                }
            } else { // 이전 수와 다르면 cnt 초기화
                nums[lp] = nums[rp];
                lp++;
                cnt = 1;
            }
        }

        return lp;
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하였으므로 시간 복잡도는 O(N)이다. N은 최대 30,000 이므로 감당할 수 있는 범위이다.

 

✍️ 성능 회고

시간 복잡도는 O(N)으로 나쁘지 않지만 깔끔한 코드라고 생각되지는 않는다.

 

💡 무엇을/어떻게 개선할 수 있을까?

현재 코드에서는 nums[lp] = nums[rp]; 와 lp++; 이 두 번 사용된다. 연속되는 수를 세는 cnt 변수를 이용하는 것 외에 다른 방법을 사용한다면 중복 코드를 없앨 수 있지 않을까.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

중복을 최대 두 개까지 허용한다고 했으므로 바로 이전 수(nums[lp-1])가 아닌 nums[lp-2]와 비교할 수 있다.

이 방법을 사용한다면 특정 원소가 몇 번 중복되는지 카운트 할 필요가 없다.

class Solution {
    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;
    }
}

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하였으므로 마찬가지로 시간 복잡도는 O(N)이다.

 

🛠 내 코드에 적용해보기

문제에서 중복 허용이 두 개까지 되기 때문에 중복 값의 수를 세는 cnt 변수를 만들었었는데,

cnt 변수를 사용하지 않고, nums[rp]와 nums[lp-2]가 같지 않다면 중복이 최소 3개 이상인 것으로 판단할 수 있다.

class Solution {
    public int removeDuplicates(int[] nums) {
    	// 중복 2개까지 허용하니 배열의 길이가 2이하라면 그대로 리턴 
        if (nums.length <= 2) {
            return nums.length;
        }

        int lp = 2;
        for (int rp = 1; rp < nums.length; rp++) {
            if (nums[rp] != nums[lp-2]) { // 같지 않을 때만 대입하고 lp 갱신
                nums[lp] = nums[rp];
                lp++;
            }
            // 같다면 lp는 갱신하지 않고 rp만 갱신한다
        }

        return lp;
    }
}

중복이 없는 효율적인 코드로 개선할 수 있었다.

 

느낀 점

문제를 읽자마자 생각나는 방법은 카운트 변수를 두는 것이었는데, 앞으로 문제를 많이 풀어 비슷한 유형에 익숙해진다면 nums[lp-2]와 비교할 생각을 할 수 있지 않을까.