[LeetCode Top Interview 150]
[문제 링크]
[문제 설명]
오름차순으로 정렬된 정수 배열이 주어지면,
각 요소가 한 번씩만 나타나도록 배열에서 중복 값을 제자리에서 제거
순서는 동일하게 유지되어야 한다.
단, nums의 첫 번째 요소가 처음 nums에 있었던 순서대로 포함해야 한다.
[예시1]
입력: nums = [1,1,2] 출력: 2, nums = [1,2,_] 설명: 함수는 k = 2를 반환해야 하며 nums의 처음 두 요소는 각각 1과 2입니다. 반환된 k 외에 무엇을 남겨두는지는 중요하지 않습니다(따라서 밑줄로 표시됩니다).
[예시2]
입력: 숫자 = [0,0,1,1,1,2,2,3,3,4] 출력: 5, 숫자 = [0,1,2,3,4,_,_,_,_, _] 설명: 함수는 k = 5를 반환해야 하며, nums의 처음 5개 요소는 각각 0, 1, 2, 3, 4입니다. 반환된 k 외에 무엇을 남겨두는지는 중요하지 않습니다(따라서 밑줄로 표시됩니다).
[제약]
- 1 <= nums.length <= 3 * 104
- 100 <= nums[i] <= 100
- nums 내림차순으로 정렬되지 않음.
[어떻게 풀지 고민해보기]
사실 문제 자체를 이해하는데 꽤 오랜 시간이 소요됐다.
중복 값을 완전히 다 제거하고 깨끗하게 배열을 출력해야 되는 거라고 생각했었는데 예시를 보니까 그게 아니었던 것이다.
그래서 다시 생각을 해봤다.
[접근 방법?]
먼저, 배열이 오름차순으로 정렬이 되어있으니까..
예를 들어서 nums 배열의 값이 [0, 1, 1, 2, 2, 2, 3] 일 경우에
각 배열의 인덱스를 비교하여 중복된 값인지 확인해봐야겠다고 생각했다.
nums[0]과 nus[1] (배열의 인덱스 0번, 1번)의 값을 비교하고, nums[1]과 nums[2]의 값을 비교하고.. 이런 식으로 말이다.
0과 1은 중복되지 않으니까 패스
1과 1은 중복이 발생하므로 어떤 처리가 필요
1과 2는 중복되지 않으니까 패스..
이런 느낌으로 풀어가야 하지 않을까? 싶었다.
if문과 for문을 먼저 사용해보자
[최종 제출 코드]
class Solution { public int removeDuplicates(int[] nums) { int r=1; for(int i=1; i<nums.length; i++){ if(nums[i-1] != nums[i]){ nums[r]=nums[i]; r++; } } return r; } }
[풀이] 초기 배열 nums = [0, 1, 1, 2, 2, 2, 3]
i=1 / r= 1 | [0, 1, 1, 2, 2, 2, 3] | true / r=2
i=2 / r= 2 | [0, 1, 1, 2, 2, 2, 3] | false / r=2
i=3 / r= 2 | [0, 1, 1, 2, 2, 2, 3] -> [0, 1, 2, 2, 2, 2, 3] | true / r=3
i=4 / r= 3 | [0, 1, 2, 2, 2, 2, 3] | false / r=3
i=5 / r= 3 | [0, 1, 2, 2, 2, 2, 3] | false / r=3
i=6 / r= 3 | [0, 1, 2, 2, 2, 2, 3] -> [0, 1, 2, 3, 2, 2, 3] | true / r=4
최종적으로 r은 4 리턴 / 중복이 제거된 최종 배열 [0, 1, 2, 3, 2, 2, 3]
최종 배열에서 길이 4만큼 출력이 된다. [0, 1, 2, 3]
