문제
문제 링크
고려해야하는 조건
1. 다른 배열을 생성하는 등의 여분의 공간을 할당하면 안됩니다. 입력 배열을 O(1) 메모리로 제자리에서 수정하여 이 작업을 수행해야 합니다.
2. 비내림차순으로 정렬된 정수 배열 nums를 받아서 고유 요소가 3번 나타나면 즉시 제거해야합니다.
3. 해당 검증을 통과해야 합니다.
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}O(1)
주어진 조건으로 알아낸 사실
-
두 번까지 고유한 값이 중복되어도 중복 즉, 제거해야하는 인덱스로 간주하지 않기 때문에
nums[i-2] 와 nums[i]이 같은지를 확인해야 합니다. (ArrayOutOfBounsIndex 에러가 발생할 수 있기 때문에 변수 k를 사용한 조건식 등의 활용을 어떻게 해야할지 고려해볼 수 있습니다.) -
비내림차순이기 때문에 두번째 이전 요소와 현재 요소가 같다면 그 사이의 중간값 또한 같을 수 밖에 없습니다.
-
기존 배열 내에서 수정이 이루어지기 때문에 배열의 크기는 변하지 않습니다. 중복을 제거한 자리에 다음 값을 당겨와서 채우도록 합니다. (이렇게 하면 중복이 제거된 개수만큼 배열의 뒤 쪽 인덱스에 값이 비어있는 상태가 될 것입니다.)
이해 기반으로 작성한 코드
public static int removeDuplicates(int[] nums) {
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (k == 1 || nums[i] == nums[k-2]) {
nums[k++] = nums[i];
}
}
return k;
}- 변수 k는 새로 배치할 배열의 인덱스를 의미합니다.
- 첫번째 요소, 두번째 요소까지는 무조건 유지시킵니다.
어려웠던 점을 해결한 과정
i = 1 일 때, 아직 증감식이 일어난 적 없기 때문에 k도 1 인 상태입니다.
그러면 if문에서 nums[1] == nums[-1] 부분이 ArrayOutOfIndexException 을 일으킬 것이라고 예측했지만, 정상적으로 실행되었습니다.
디버깅을 통해 i = 1 일 때, if문이 어떻게 흘러가는지 살펴보았습니다. || 연산자의 첫 번째 조건문이 true로 판별나면 바로 내부로 진입하여 nums[1] = nums[1]; 으로 흘러가는 것을 확인할 수 있었습니다.
||(논리 OR) 연산자는 왼쪽 조건이 true일 경우에는 오른쪽 조건을 평가하지 않고 바로 true를 반환합니다. 따라서 첫 번째 조건이 true로 판별되어 두 번째 조건을 평가하지 않고 바로 내부 블록으로 진입하게 된 것 입니다.
그래서 nums[i] == nums[k-2] 에서 nums[i] == nums[-1] 으로 접근하는 상황이 발생하지 않았고, 런타임 에러가 발생하지 않은 이유입니다.
만약에 두 번째 조건이 true로 평가되어야만 내부 블록이 실행되었다면, nums[-1] 에 접근하여 ArrayIndexOutOfException이 발생했을 것입니다.
