LeetCode 26: 정렬된 배열에서 중복을 하나씩만 남기기
정렬되어 있다는 조건을 사용합니다
오름차순으로 정렬된 배열에서 같은 값은 하나만 남기는 문제입니다. 기존 순서를 유지하고 별도 배열 없이 앞쪽에 결과를 모은 다음 고유한 값의 개수를 반환합니다.
앞서 풀었던 Remove Element처럼 남길 값을 앞으로 당기는 방식으로 생각했습니다. 이번에는 특정 값 대신 마지막으로 남긴 값과 비교하면 됩니다.
pos는 마지막으로 남긴 값의 위치입니다. 현재 값이 nums[pos]와 다르면 새로운 값이므로 pos를 한 칸 늘리고 그 자리에 저장합니다. 같은 값이면 건너뜁니다. 정렬된 배열에서는 같은 값이 붙어 있어서 이 비교로 중복을 구분할 수 있습니다.
pos는 마지막 유효한 값의 인덱스입니다. 그래서 개수인 pos + 1을 반환합니다. 코드의 마지막 주석에서는 배열 길이와 인덱스를 혼동했습니다. 이 풀이는 배열에 원소가 하나 이상 있다는 문제 조건을 전제로 첫 값을 남깁니다.
코드
class Solution {
public int removeDuplicates(int[] nums) {
// 시작 인덱스는 0부터 시작한다.
int pos = 0;
// nums 배열의 전체를 일일이 반복한다.
for(int i = 0; i < nums.length; i++){
// 만약 시작 인덱스와 현재 반복중인 배열의 요소와 다르다면?
if(nums[pos] != nums[i]){
// 시작 인덱스 바로 다음 인덱스에 반복중인 배열의 요소를 이동시킨다.
nums[++pos] = nums[i];
}
}
// nums의 길이는 최소 0부터 시작되므로, 이동시킨 횟수가 유효한 배열의 총 길이이다.
return pos + 1;
}
}