문제 설명
문제 설명: 정렬된 정수 배열 nums가 주어졌을 때, 중복된 원소를 제자리에서 제거하여 각 고유 원소가 최대 두 번씩만 나타나도록 하세요. 원소들의 상대적인 순서는 유지되어야 합니다. 일부 언어에서는 배열의 길이를 변경하는 것이 불가능하기 때문에, 결과를 배열 nums의 첫 부분에 저장해야 합니다. 구체적으로, 중복을 제거한 후 k개의 원소가 남는다면, nums의 처음 k개의 원소가 최종 결과를 담아야 합니다. k 이후의 원소들은 어떤 값이든 상관없습니다. 최종 결과를 nums의 처음 k개의 위치에 배치한 후 k를 반환하세요. 추가 배열을 할당하지 마세요. 입력 배열을 제자리에서 수정하고 O(1) 추가 메모리만 사용해야 합니다. 커스텀 판정: 판정 시스템은 다음 코드로 여러분의 솔루션을 테스트할 것입니다:
int[] nums = [...]; // 입력 배열
int[] expectedNums = [...]; // 올바른 길이를 가진 예상 답안
int k = removeDuplicates(nums); // 구현한 함수 호출
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
모든 단언문이 통과하면, 여러분의 솔루션은 승인됩니다.
예제
예제 1
예제 2
예제 3
예제 4
⚠️제약 조건
- •
1 <= nums.length <= 3 * 104 - •
-104 <= nums[i] <= 104 - •
nums는 비내림차순으로 정렬되어 있습니다.
해결 방법
🎯접근 방식
이 문제는 정렬된 배열에서 각 원소가 최대 두 번까지만 나타나도록 중복을 제거하는 문제입니다. 주어진 해결 방법은 해시맵을 사용하여 각 숫자의 빈도를 추적하고, 빈도가 2 이하인 경우에만 배열의 앞부분에 배치하는 방식입니다. 핵심 아이디어는 해시맵을 통해 중복 횟수를 관리하면서, 배열을 인덱스 포인터를 사용해 제자리에서 수정하는 것입니다.
솔루션 코드
복잡도 분석
O(n)O(n)💡상세 설명
이 문제는 정렬된 정수 배열 nums에서 중복된 요소를 제거하여 각 고유 요소가 최대 두 번씩만 나타나도록 하는 것입니다. 배열의 상대적인 순서는 유지해야 하며, 추가적인 배열을 할당하지 않고 주어진 배열을 제자리에서 수정하여 해결해야 합니다.
이 문제를 해결하기 위한 알고리즘의 핵심 아이디어는 배열을 한 번 순회하면서 각 요소의 등장 횟수를 추적하고, 각 요소가 두 번 이하로 나타날 때만 배열의 앞부분에 배치하는 것입니다.
이제 코드의 주요 로직을 단계별로 설명하겠습니다.
코드 설명
-
변수 초기화
let count = {}; let p = 0;count는 각 숫자의 등장 횟수를 기록하기 위한 객체입니다.p는 새로운 배열의 "유효한" 끝을 가리키는 포인터 역할을 합니다. 이 포인터는 중복을 제거한 후 배열의 새로운 길이를 나타내게 됩니다.
-
배열 순회
for (let num of nums) {nums배열을 처음부터 끝까지 순회합니다. 각 요소num에 대해 작업을 수행합니다.
-
등장 횟수 기록 및 조건 확인
count[num] = (count[num] || 0) + 1; if (count[num] <= 2) { nums[p] = num; p++; }count[num] = (count[num] || 0) + 1;는 현재 숫자의 등장 횟수를 증가시킵니다.count[num]이 정의되지 않은 경우에는0으로 초기화합니다.if (count[num] <= 2)조건문은 현재 숫자가 두 번 이하로 나타났는지 확인합니다.- 조건이 참이라면,
nums[p] = num;을 통해 현재 숫자를 배열의p위치에 저장하고,p를 증가시켜 다음 위치를 준비합니다.
-
결과 반환
return p;- 배열을 모두 순회한 후,
p는 중복을 제거한 후의 배열 길이를 나타냅니다. 이 값을 반환하여 문제에서 요구한k값을 제공합니다.
- 배열을 모두 순회한 후,
핵심 변수들의 역할
count: 각 숫자의 등장 횟수를 저장하여, 각 숫자가 최대 두 번까지만 배열에 포함되도록 합니다.p: 새로운 배열의 유효한 길이를 나타내며, 중복된 요소를 제거한 후 배열의 끝을 가리킵니다.
왜 이 방법이 효과적인가?
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 각 숫자의 등장 횟수를 추적하여 두 번 이하로 나타날 때만 배열에 포함시키므로, 문제의 요구사항을 충족시킵니다. 또한, 추가적인 배열을 사용하지 않고 주어진 배열을 제자리에서 수정하므로 공간 복잡도는 O(1)입니다. 이러한 효율성 때문에 이 방법은 문제 해결에 효과적입니다.