80.Remove Duplicates from Sorted Array ll
문제
정수 배열 nums가 오름차순으로 정렬되어 있습니다. 이 배열에서 각 고유한 요소가 최대 두 번 나타나도록 중복된 요소를 제거하여야 합니다. 요소의 상대적인 순서는 유지되어야 합니다.
일부 언어에서 배열의 길이를 변경할 수 없으므로 대신 결과를 배열 nums의 첫 부분에 배치해야 합니다. 더 정확하게는, 중복된 요소를 제거한 후 k개의 요소가 남는다면, 배열 nums의 처음 k개 요소는 최종 결과를 담아야 합니다. 처음 k개 요소 이후에 나머지 요소는 무시해도 됩니다.
배열에 대해 추가적인 공간을 할당해서는 안 됩니다. 대신 입력 배열을 장소를 수정하여 O(1)의 추가 메모리만 사용하여 작업해야 합니다.
첫 k개 슬롯에 최종 결과를 배치한 후, k를 반환하세요.
개인적인 느낌 또는 기타 정보
- 소요시간: 3시간 15분
- 쉽지 않다. 적절한 방법이 떠오르지 않아서 덕지덕지 코드를 짰다. 해결을 하긴 했지만 찝찝하다. 성능도 굉장히 좋지 않은 코드를 짰다.
- 풀이 계획이 잘 떠오르지 않았다.
의사코드 또는 풀이 계획
1. 배열을 순회하면서 요소와 중복되는 요소의 개수를 찾는다.
2. 중복되는 요소의 개수가 2개 초과인 경우과 그렇지 않은 경우를 분기처리한다.
3. 중복되는 요소가 2개 초과인 경우
3-1. 중복이 되어서 지울 index를 찾는다.
3-2. 현재의 값과 중복되지 않는 값의 index를 찾는다.
3-3. 중복이 되어서 지울 index에 3-2에서 찾은 값을 순차적으로 복사한다. 단, nums 배열이 모두 하나의 값으로 이루어져있을 경우, 복사할 값이 없으므로 3-1에서 찾은 중복이 되어서 지울 index를 -1000001로 채워넣는다. 그리고 break 한다.
3-4. nums 배열이 여러 개의 값으로 이루어져있을 경우에는 3-2에서 찾은 중복되지 않는 값의 index에서부터 nums 배열의 끝까지 -1000001로 채워넣는다.
4. 중복되는 요소가 2개 이하인 경우
4-1. 아무 처리를 할 것이 없으므로 현재의 요소와 다른 요소가 나올 때 까지 넘긴다.
5. nums 배열에서 유효한 값이 들어있는 최대 index를 찾는다. nums 배열에서 처음으로 -1000001을 만나는 경우, 해당 index가 nums 배열에서 유효한 index이다. -1000001이 없는 경우는 nums배열의 길이를 그대로 반환한다.int result(nums배열 유효범위 가리킬 변수) = 0;
int lp(nums배열 순회 위한 포인터) = 0;
while(lp < nums 길이)
같은 값 counter = 0;
현재 포인터가 가리키는 값 = nums[lp];
// nums 배열에서 같은 값이 몇 개 존재하는지 확인
for (int index = lp; nums 전체 길이보다 작아야 한다; index 1씩 증가)
if(현재 포인터가 가리키는 값과 nums[index]가 같다)
같은 값 counter++;
if (같은 값이 2개보다 많으면)
지워야할인덱스 = lp + 2; //
현재 포인터가 가리키는 값과 다른 값이 존재하는 인덱스 = 0;
현재 포인터부터 시작해서 반복문 돌면서 nums 배열 순회한 후 현재 값과 다른 값이 존재하는 index 찾기
for (index = 포인터; nums의 길이; index++)
if(현재 포인터가 가리키는 값과 nums[index]가 다르면)
현재 포인터가 가리키는 값과 다른 값이 존재하는 인덱스 = index;
break;
if (만약에 다른 값이 존재하는 인덱스가 0이면) // nums배열이 하나의 값으로만 이루어졌을 경우
for (index = 지워야할 index; nums의 길이; index++)
nums[index] = -1000001;
break;
int 임시인덱스 = 현재 포인터가 가리키는 값과 다른 값이 존재하는 인덱스 - 지워야할 인덱스;
// 2개 이상 중복된 값의 자리에 nums 배열의 뒷부분을 앞으로 복사한다.
for (index = 현재 포인토가 가리키는 값과 다른 값이 존재하는 인덱스; nums의 길이; index++)
nums[지워야할 인덱스] = nums[index];
지워야할 인덱스++;
for (index = nums의 길이 - 임시 인덱스; nums의 길이; i++)
nums[index] = -1000001;
if (같은 값이 2개보다 이하면)
for (index = 포인터; nums의 길이; index++)
if (포인터가 가리키는 값과 nums[index]가 같으면)
포인터++;
// nums 배열에서 유효한 index 찾기
for (index = 0; nums 길이; index++)
if (nums[index]가 -1000001과 같으면)
result = i;
break;
else
result = nums의 길이;
return result;풀이
class Solution {
public int removeDuplicates(int[] nums) {
int result = 0; // nums 배열에서 유효한 index를 가리킬 변수
int lp = 0; // nums 배열을 순회하기 위한 pointer
while (lp < nums.length) {
int cnt = 0;
int cur = nums[lp];
for (int index = lp; index < nums.length; index++) {
if (cur == nums[index]) {
cnt++;
}
}
if (cnt > 2) {
int indexToDelete = lp + 2;
int differValueIndex = 0;
for (int index = lp; index < nums.length; index++) {
if (cur != nums[index]) {
differValueIndex = index;
break;
}
}
if (differValueIndex == 0) {
for (int i = indexToDelete; i < nums.length; i++) {
nums[i] = -1000001;
}
break;
}
int tempIndex = differValueIndex - indexToDelete;
for (int index = differValueIndex; index < nums.length; index++) {
nums[indexToDelete] = nums[index];
indexToDelete++;
}
for (int i = nums.length - tempIndex; i < nums.length; i++) {
nums[i] = -1000001;
}
}
if (cnt <= 2) {
for (int index = lp; index < nums.length; index++) {
if (cur == nums[index]) {
lp++;
}
}
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == -1000001) {
result = i;
break;
} else {
result = nums.length;
}
}
return result;
}
}다른 풀이
난 무슨 짓을 한거지?
다른 풀이를 보고 코드를 분석하면 왜 그런지 알겠지만, 내가 다시 구현하라고 하면 못할 것 같다. 투포인터와 슬라이딩윈도우를 사용한 것 같은데, 이 두 가지 개념은 단순한 문제에서는 알겠는데 그 외에는 적용이 쉽지 않다.
public int removeDuplicates(int[] nums) {
int i = 0;
for (int n : nums)
if (i < 2 || n > nums[i - 2])
nums[i++] = n;
return i;
}
public int removeDuplicates(int[] nums) {
int i = 2;
for (int j = 2; j < nums.length; j++)
if (nums[j] != nums[i-2])
nums[i++] = nums[j];
return i;
}
