Week 1-1. [Array / String] 26. Remove Duplicates from Sorted Array

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Remove Duplicates from Sorted Array - LeetCode

주어진 배열에서 중복되는 원소를 제거하라.

• 입력
  • nums | int arrray := 중복된 원소가 포함된 배열, | nums | ∈ [1, 3 * 10^4]
    
• 출력
  • k | int := nums 배열에서 unique 한 원소의 개수
• 조건
  • | nums[i] | ∈ [-100, 100]
  • nums 배열은 오름차순 정렬되어 있다.

 

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

Two Pointer 방식을 생각했다.

처음에는 visited 배열을 하나 생성한다. 그리고 rp로 nums 배열을 순회하면서 한 번 이상 나온 원소는 visited 배열에 체크해둔다.

visited 배열에 체크되지 않은 원소들을 lp에 저장한다.

 

결론적으로는 문제에서 주어지는 nums 배열은 오름차순으로 정렬되어있기 때문에 Two Pointer를 사용하지 않고 단순하게 해결할 수 있었다.

 

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

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

 

📝 의사 코드

visited = -100부터 100까지 수를 나타내는 배열
lp, rp = 0, 0

while (rp가 nums를 넘지 않는 동안) {
	if (visited[nums[rp]]가 체크되어 있지 않으면) {
    	nums[lp]에 nums[rp]를 대입한다.
        lp++;
    }
    rp++;
}

 

🎯 구현 코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int[] visited = new int[201];
        int lp = 0;
        int rp = 0;

        while (rp < nums.length) {
            if (nums[rp] >= 0 && visited[nums[rp]] == 0) {
                visited[nums[rp]] = 1;
                nums[lp] = nums[rp];
                lp++;
            } else if (nums[rp] < 0 && visited[-(nums[rp]-100)] == 0) {
                visited[-(nums[rp]-100)] = 1;
                nums[lp] = nums[rp];
                lp++;
            }
            rp++;
        }
        
        return lp;
    }
}

 

내 코드를 탐구해보기

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

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

 

✍️ 성능 회고

시간 복잡도는 O(N)으로 나쁘지 않지만 코드가 복잡하다.

 

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

문제에서 nums는 이미 오름차순 정렬되어 있다고 했다. 해당 조건을 놓쳤다ㅜ

그렇다면 값을 체크하는 visited 배열을 사용하지 않고 단순히 바로 이전 값과 비교하여 해결할 수 있다.

 

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

🎯 구현 코드

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

 

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

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

 

🛠 내 코드에 적용해보기

문제에서 nums는 이미 오름차순 정렬되어 있다고 했다.

 

그렇다면 값을 체크하는 visited 배열을 사용하지 않고 단순히 바로 이전 값과 비교하여 해결할 수 있다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int lp = 1;
        int rp = 1;

        while (rp < nums.length) {
            if (nums[rp] != nums[lp-1]) {
                nums[lp] = nums[rp];
                lp++;
            }
            rp++;
        }
        
        return lp;
    }
}

 

느낀 점

더욱 쉽고 간결하게 구현할 수 있는 문제였는데 사소한 조건을 놓쳐 시간도 오래 걸리고 코드도 복잡해졌다.

앞으로는 조건 하나를 놓쳐 어렵게 생각하는 일이 없도록 문제를 꼼꼼히 읽자!