문제 설명
문제 설명: 두 개의 정수 배열 nums1과 nums2가 오름차순으로 정렬되어 있으며, m과 n은 각각 nums1과 nums2의 요소 개수를 나타냅니다. nums1과 nums2를 하나의 배열로 오름차순으로 병합하세요. 최종 정렬된 배열은 함수에서 반환되지 않고, 대신 배열 nums1에 저장되어야 합니다. 이를 위해 nums1의 길이는 m + n이며, 처음 m개의 요소는 병합할 요소들이고, 마지막 n개의 요소는 0으로 초기화되어 무시해야 합니다. nums2의 길이는 n입니다.
예제
예제 1
예제 2
예제 3
예제 4
예제 5
예제 6
⚠️제약 조건
- •
nums1.length == m + n - •
nums2.length == n - •
0 <= m, n <= 200 - •
1 <= m + n <= 200 - •
-109 <= nums1[i], nums2[j] <= 109
해결 방법
🎯접근 방식
이 문제는 두 개의 정렬된 배열을 병합하는 문제로, 투 포인터 알고리즘을 사용하여 해결합니다. nums1의 끝에서부터 시작하여 두 배열의 요소를 비교하면서 큰 값을 뒤에서부터 채워나가는 방식으로 접근합니다. 핵심 아이디어는 nums1의 추가 공간을 활용하여 뒤에서부터 병합함으로써, nums1의 기존 요소를 덮어쓰지 않고 효율적으로 병합하는 것입니다.
솔루션 코드
복잡도 분석
O(m + n)O(1)💡상세 설명
이 문제는 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 문제입니다. 여기서 중요한 점은 결과 배열이 nums1에 저장되어야 하며, nums1의 크기는 이미 m + n으로 할당되어 있다는 것입니다. nums1의 뒤쪽에는 0으로 초기화된 공간이 있어, nums2의 요소를 수용할 수 있습니다.
이제 주어진 코드를 단계별로 설명하겠습니다.
1. 알고리즘의 핵심 아이디어
이 알고리즘은 두 배열의 끝에서부터 시작하여 가장 큰 요소를 선택해 nums1의 뒤쪽부터 채워나가는 방식입니다. 이렇게 하면 추가적인 공간 없이도 두 배열을 병합할 수 있습니다. nums1의 뒤쪽에 여유 공간이 있기 때문에, 뒤에서부터 채우는 것이 가능합니다.
2. 코드의 주요 로직 설명
-
포인터 설정:
p1,p2,p라는 세 개의 포인터를 사용합니다.p1은nums1의 유효한 마지막 요소의 인덱스를 가리킵니다. (m - 1)p2는nums2의 마지막 요소의 인덱스를 가리킵니다. (n - 1)p는nums1의 전체 길이에서 마지막 인덱스를 가리킵니다. (m + n - 1)
-
병합 과정:
p2가 0 이상인 동안 반복문을 실행합니다. 이는nums2의 모든 요소가nums1에 병합될 때까지 반복한다는 의미입니다.nums1[p1]이nums2[p2]보다 크다면,nums1[p]에nums1[p1]을 복사하고p1과p를 각각 감소시킵니다.- 그렇지 않다면,
nums1[p]에nums2[p2]를 복사하고p2와p를 각각 감소시킵니다. - 이 과정을 통해
nums1의 뒤쪽부터 가장 큰 값을 채워나가게 됩니다.
3. 각 단계별 동작 과정
- 초기화: 포인터
p1,p2,p를 설정합니다. - 반복문 실행:
p2가 0 이상인 동안 반복합니다.nums1[p1]과nums2[p2]를 비교하여 더 큰 값을nums1[p]에 저장합니다.- 포인터를 적절히 감소시켜 다음 위치를 준비합니다.
- 종료:
p2가 음수가 되면nums2의 모든 요소가nums1에 병합된 상태가 됩니다.
4. 핵심 변수들의 역할
p1:nums1의 현재 비교할 요소의 인덱스.p2:nums2의 현재 비교할 요소의 인덱스.p:nums1의 현재 채울 위치의 인덱스.
5. 왜 이 방법이 효과적인지
이 방법은 두 배열이 이미 정렬되어 있다는 특성을 이용하여, 추가적인 메모리 사용 없이 nums1의 뒤쪽부터 큰 요소를 채워나감으로써 효율적으로 병합을 수행합니다. 이렇게 하면 O(m + n)의 시간 복잡도로 문제를 해결할 수 있으며, 이는 두 배열의 모든 요소를 한 번씩만 비교하고 이동시키는 최적의 방법입니다.
이러한 접근 방식은 공간 복잡도를 최소화하면서도 효율적인 정렬을 가능하게 합니다.