문제 설명
문제 설명: 정수 배열 nums와 정수 val이 주어졌을 때, nums에서 val의 모든 발생을 제자리에서 제거하세요. 요소의 순서는 변경될 수 있습니다. 마지막으로, nums에서 val과 같지 않은 요소의 개수를 반환하세요. k를 nums에서 val과 같지 않은 요소의 개수라고 합시다. 정확성을 보장하기 위해 다음을 수행해야 합니다:
- 배열 nums를 수정하여 nums의 처음 k개의 요소가 val과 같지 않은 모든 요소를 포함하도록 하세요. nums의 나머지 요소는 무시해도 됩니다.
- k를 반환하세요. 커스텀 판정: 판정자는 다음 코드로 당신의 솔루션을 테스트할 것입니다:
int[] nums = [...]; // 입력 배열
int val = ...; // 제거할 값
int[] expectedNums = [...]; // 올바른 길이를 가진 예상 답안.
// val 값을 포함하지 않습니다.
int k = removeElement(nums, val); // 구현한 함수를 호출합니다.
assert k == expectedNums.length;
sort(nums, 0, k); // nums의 처음 k개의 요소를 정렬합니다.
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
모든 단언이 통과하면, 당신의 솔루션은 승인될 것입니다.
예제
예제 1
예제 2
⚠️제약 조건
- •
0 <= nums.length <= 100 - •
0 <= nums[i] <= 50 - •
0 <= val <= 100
해결 방법
🎯접근 방식
이 문제는 배열을 순회하면서 주어진 값 val과 다른 요소들을 앞쪽으로 이동시키는 방식으로 해결합니다. 이 과정에서 두 개의 포인터를 사용하여 val이 아닌 요소들을 배열의 앞부분에 차례로 배치하고, 그 개수를 반환합니다. 핵심 아이디어는 val이 아닌 요소들을 유지하면서 배열을 덮어쓰는 방식으로 불필요한 요소들을 제거하는 것입니다.
솔루션 코드
복잡도 분석
O(n)O(1)💡상세 설명
이 문제는 주어진 배열에서 특정 값을 제거하고, 그 결과를 배열의 앞부분에 모아두는 작업을 수행하는 것입니다. 이 작업은 배열을 제자리에서(in-place) 수행해야 하며, 최종적으로 제거되지 않은 요소의 개수를 반환해야 합니다. 이제 이 문제를 해결하는 코드에 대해 자세히 설명해 보겠습니다.
1. 알고리즘의 핵심 아이디어
이 알고리즘의 핵심 아이디어는 두 개의 포인터를 사용하는 것입니다. 하나의 포인터는 배열을 순회하면서 현재 요소가 제거해야 할 값인지 확인하고, 다른 하나의 포인터는 제거되지 않은 요소를 배열의 앞부분에 채워 넣는 역할을 합니다. 이렇게 하면, 불필요한 요소들을 배열의 뒤쪽으로 밀어내지 않고도 원하는 결과를 얻을 수 있습니다.
2. 코드의 주요 로직 설명
코드의 주요 로직은 다음과 같습니다:
k라는 변수를 사용하여 제거되지 않은 요소를 저장할 위치를 추적합니다.- 배열을 처음부터 끝까지 순회하면서, 현재 요소가 제거할 값(
val)과 다른지 확인합니다. - 만약 다르다면, 현재 요소를
k위치에 저장하고k를 증가시킵니다. - 배열 순회가 끝나면
k는 제거되지 않은 요소의 개수를 나타내며, 이 값을 반환합니다.
3. 각 단계별 동작 과정
-
초기화:
k를 0으로 초기화합니다. 이는 제거되지 않은 요소를 저장할 시작 위치를 나타냅니다. -
배열 순회:
for루프를 사용하여 배열의 각 요소를 순회합니다.i는 현재 요소의 인덱스를 나타냅니다.
-
조건 확인:
if (nums[i] !== val)조건문을 사용하여 현재 요소가 제거해야 할 값이 아닌지 확인합니다.- 만약 현재 요소가
val과 다르다면, 이는 우리가 보존해야 할 요소입니다.
- 만약 현재 요소가
-
요소 저장 및 포인터 이동:
nums[k] = nums[i]를 통해 현재 요소를k위치에 저장합니다.k++를 통해 다음 저장 위치로 이동합니다.
-
결과 반환: 배열 순회가 끝나면
k를 반환합니다. 이 값은 제거되지 않은 요소의 개수이며, 배열의 앞부분에 이 요소들이 모여 있습니다.
4. 핵심 변수들의 역할
k: 제거되지 않은 요소를 저장할 위치를 추적합니다. 최종적으로 제거되지 않은 요소의 개수를 나타내는 값이 됩니다.i: 배열을 순회하기 위한 인덱스입니다. 각 요소를 검사하여val과 다른지 확인합니다.
5. 왜 이 방법이 효과적인지
이 방법은 매우 효율적입니다. 왜냐하면:
- 시간 복잡도: 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 이는 매우 효율적입니다.
- 공간 복잡도: 추가적인 배열을 사용하지 않고, 주어진 배열 내에서 작업을 수행하므로 공간 복잡도는 O(1)입니다.
- 직관적: 두 개의 포인터를 사용하여 배열을 순회하고 필요한 요소를 앞부분에 모으는 방식은 직관적이며 구현이 간단합니다.
이렇게 해서 문제의 요구사항을 충족하면서도 효율적인 방법으로 문제를 해결할 수 있습니다.