정렬된 배열에서 중복된 원소를 제거하는 문제를 풀었다. 코딩 인터뷰 관점에서 문제
해결 과정을 brute force 방법부터 시간, 공간 복잡도를 고려하는 과정까지
순서대로 정리하고 python/C++ 최적 Solution까지 정리해 봤다.
Easy Collection - Top Interview Questions - Array
Remove Duplicates from Sorted Array
리트코드 문제 링크
Solution 바로보기
First Approach (5분)
-
문제 이해
중복을 제거하는데, 순서는 그대로 유지해야 된다.
중복 제거된 후의 개수 K를 return 하고, 처음 주어진 array의 배열 크기는
그대로 두어도 된다. K 뒤로 오는 배열 안의 원소는 don't care
배열을 추가로 선언하면 안 되고 주어진 배열 안에서 수정해야 한다. O(1) extra
memory
문제를 명확히 하기 위한 과정(Q&A)
-
생각나는 알고리즘/자료구조
앞의 원소는 그대로 두고, 뒤에 나오는 원소는 뒤로 이동시킨다.
뒤로
보내면 뒤쪽 index도 가지고 있어야 됨
앞에서부터 순회, 뒤에 교체된 index 가 K가 될 것 같다.
처음 K는 nums array length로 시작?
First Solution(brute force)
index i = 0부터 중복되는 count를 세면서 순회하고, K 는 N(nums array의 length)
중복되는 count만큼 K = N - count
i + 1에 i + count + 1 부터 가져옴
다음 i++ 부터 다시 순회 시작
Second Solution
순회하면서 중복되는 원소를 곧바로 제거하고, 뒤에 있는 원소들을 앞으로
이동시키는 작업이 불필요하다는 생각이 들었다.
O(1) 이기 때문에, 주어진 배열 안에 중복되지 않는 다음 원소의 index를 mark 할 수
있는 방법을 생각했다.
Constraints가 `-100 <= nums[i] <= 100` 이므로, 101/102/.. 로 mark 하는
방식을 생각해 봤다.
Accepted Solution
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
start_idx = 0
count = 0
k = len(nums)
for i in range(start_idx + 1, len(nums)):
current_num = nums[start_idx]
if current_num == nums[i]:
count += 1
k -= 1
nums[start_idx + 1] = 100 + count
elif count > 0:
nums[start_idx + 1] = 100 + count
start_idx = i
count = 0
else:
start_idx = i
count = 0
next_idx= 0
for i in range(len(nums)):
if next_idx >= len(nums):
break
if nums[next_idx] > 100:
count = nums[next_idx] - 100
next_idx = next_idx + count
if next_idx >= len(nums):
break
nums[i] = nums[next_idx]
else:
nums[i] = nums[next_idx]
next_idx+=1
return k
너무 복잡하게 생각해서, 시간 안에 정확히 해결하지 못했다. 유사한 답은 나왔지만
index, count 방식에서 실수가 있었다. Hint를 봤을 때 접근 방식이나 문제풀이
방법이 잘못되진 않았지만, 훨씬 더 간단하게 풀 수 있는 문제였다.
Corner Testcase
[1, 1]
우선, Solution을 확인하기 전까진 위와 같이 복잡하게 index 2개를 이용하다 보니
코너 케이스에서 계속 통과가 안됐다. Out of range error도 종종 발생했다.
몇 년 만에 알고리즘 문제를 푸는 것이라서, 연습이 많이 필요한 부분인 것 같다.
Result
361 / 361 test cases passed.
Status: Accepted
Runtime: 126 ms
Memory Usage: 15.8 MB
Submitted: 0 minutes ago
Approach & Solution
Approach
-
Hint #1
정렬된 배열이 입력되므로, 요소의 첫 번째 위치만 알면 된다.
-
Hint #2
배열을 제자리에서 수정해야 하며 최종 배열의 크기는 잠재적으로 입력 배열의 크기보다 작을 수 있습니다. 따라서 2개의 pointer가 필요하다. 하나는 원래 배열의 현재 원소를 추적하는 것이고 다른 하나는 Unique 한 원소를 추적하기 위한 것이다.
-
Hint #3
기본적으로 중복 항목을 건너뛰고 다음 고유 원소로 넘어가면 된다.
Approach: Two Pointers
Algorithm
Since the array is already sorted, we can keep two pointers i and j, where i is the slow-runner while j is the fast-runner. As long as nums[i]=nums[j], we increment j to skip the duplicate.
When we encounter nums[j]=nums[i], the duplicate run has ended so we must copy its value to nums[i+1]. i is then incremented and we repeat the same process again until j reaches the end of array.
ex) [0, 1, 1, 1, 2, 3]
nums[i]와 nums[j]가 다를 때, nums[i+1]에 nums[j]를 대입
|
|
0
|
1
|
1
|
1
|
2
|
3
|
|
1
|
i
|
j
|
|
|
|
|
|
2
|
|
i
|
j
|
|
|
|
|
3
|
|
i
|
|
j
|
|
|
|
4
|
|
i
|
|
|
j
|
|
|
5
|
|
|
i
|
|
|
j
|
|
|
0
|
1
|
2
|
3
|
2
|
3
|
Solution
Solution을 보고 나니, 이렇게 간단한 것을 왜 이렇게까지 복잡하게 풀었나 싶었다.
python runtime 68.0(ms)
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
prev = nums[0]
idx = 0
for i in nums:
if nums[idx] != i:
idx+=1
nums[idx] = i
del nums[idx+1:]
python runtime 119.0(ms)
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
Java
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
Result
|
|
Spent Time
|
Result
|
|
1st
|
50min
|
Fail
|
|
2nd
|
30min
|
Accepted
|
|
3rd
|
-
|
-
|
|
최적화
|
-
|
-
|
|
Solution 학습
|
60min
|
-
|
|
Retry Date
|
2022/08/29
|
|
