Merge Sorted Array
정수 배열 nums1과 nums2를 받습니다. 두 배열은 각각 이미 비내림차순으로 정렬되어 있습니다. 두 배열의 모든 값을 비내림차순으로 담은 하나의 배열을 반환하세요. 두 배열 모두에 나타나는 값은 두 배열에 나타난 총횟수만큼 결과에 포함됩니다.
함수
- nums1integer-array
- 첫 번째 정렬된 배열
- nums2integer-array
- 두 번째 정렬된 배열
- 반환값integer-array
- 두 배열의 모든 값을 길이가 nums1.length + nums2.length인 하나의 정렬된 배열에
제약 조건
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1과nums2는 각각 비내림차순으로 정렬되어 있습니다.
예제
- 입력
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- 출력
- [1, 2, 3, 4, 9, 10]
- 설명
- 두 배열의 맨 앞 값을 비교해 더 작은 값을 유지하세요. 1, 그다음
nums2의 2와 3, 이어서nums1의 4와 9, 마지막으로 10입니다. 결과에는 여섯 값이 모두 들어 있습니다.
- 입력
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- 출력
- [-5, 0, 0, 0, 6, 8]
- 설명
- 0은
nums1에 두 번,nums2에 한 번 나타나므로 결과에는 0이 세 개 있습니다. -5는nums2의 모든 값보다 작으므로 맨 앞에 옵니다.
- 입력
- nums1 = [7]nums2 = [3]
- 출력
- [3, 7]
- 설명
- 각 배열에는 값이 하나씩 들어 있습니다. 3은 7보다 작으므로 먼저 옵니다.
제출 시 숨은 테스트 +13개
후속 질문
총 N개의 값을 담고 있는 정렬된 배열 k개를 O(N log k) 시간에 병합할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
두 배열은 이미 정렬되어 있습니다. 전체 결과에서 가장 작은 값은 어디에 있을까요?
남아 있는 가장 작은 값은 항상
nums1또는nums2의 맨 앞에 있습니다. 각 배열의 맨 앞 위치를 표시할 인덱스를 하나씩 유지하세요.두 배열의 앞부분을 비교하고, 더 작은 쪽을 추가한 다음 해당 인덱스를 앞으로 이동하세요. 한 배열이 소진되면 다른 배열의 나머지 부분은 이미 정렬되어 있으므로 그대로 추가하세요.
풀이
배열을 이어 붙인 다음 정렬하면 올바른 답을 얻을 수 있지만, 두 배열이 이미 정렬되어 있다는 사실을 활용하지 못합니다. 전체에서 남아 있는 가장 작은 값은 항상 두 배열 중 하나의 맨 앞에 있습니다. 배열마다 인덱스를 하나씩 두고 매 단계마다 앞에 있는 값 중 더 작은 값을 선택하면, 한 번의 순회로 결과를 만들 수 있습니다. 이것이 병합 정렬의 병합 단계입니다.
연결하고 정렬하기
핵심 아이디어
nums1의 모든 값과 nums2의 모든 값을 하나의 배열에 넣은 다음 정렬하세요. 결과에는 올바른 값이 각각 나타난 횟수만큼 올바른 순서로 들어 있습니다.
[1, 4, 9]와 [2, 3, 10]을 합친 배열은 [1, 4, 9, 2, 3, 10]이고, 정렬하면 [1, 2, 3, 4, 9, 10]이 됩니다.
nums1에 m개의 값이 있고 nums2에 n개의 값이 있을 때, 일반적인 정렬의 비용은 O((m + n) log(m + n))입니다. 이 방법은 작동하고 주어진 제한에서는 충분히 빠르지만, 이미 주어진 정렬된 순서를 활용하지 않습니다. 다음 방법은 정렬된 순서를 활용해 로그 인자를 없앱니다.
알고리즘
nums1의 값 뒤에nums2의 값을 이어 붙여 배열을 만드세요.- 숫자를 오름차순으로 정렬하세요.
- 배열을 반환하세요.
def merge(nums1, nums2):
return sorted(nums1 + nums2)포인터 두 개, 배열마다 하나씩
핵심 아이디어
nums1의 인덱스 i와 nums2의 인덱스 j를 유지하고, 둘 다 0에서 시작합니다. i 앞과 j 앞의 모든 값은 이미 결과에 들어 있습니다. 아직 사용하지 않은 값 중 가장 작은 값은 nums1[i] 또는 nums2[j]입니다. 각 배열은 정렬되어 있고 남은 값은 더 클 수밖에 없기 때문입니다. 더 작은 값을 추가하고 해당 인덱스를 이동합니다.
[1, 4, 9]와 [2, 3, 10]의 경우: 1이 2보다 작고, 다음으로 2가 4보다 작으며, 3이 4보다 작고, 4가 10보다 작으며, 9가 10보다 작습니다. 이제 nums1을 모두 사용했으므로 [10]인 nums2의 나머지를 그대로 복사합니다. 결과는 [1, 2, 3, 4, 9, 10]입니다.
각 단계에서 값 하나를 기록하므로 반복문은 m + n번 실행됩니다. 시간 복잡도는 O(m + n)입니다. 결과 배열이 유일한 추가 메모리입니다.
알고리즘
i와j를 0으로 설정하고 빈 결과를 만드세요.- 두 배열에 모두 남은 값이 있는 동안
nums1[i]와nums2[j]를 비교하세요. - 더 작은 값을 추가하고 해당 인덱스를 다음으로 이동하세요. 값이 같으면
nums1[i]를 선택하세요. - 한 배열이 모두 소진되면 다른 배열에 남은 값을 추가하세요.
- 결과를 반환하세요.
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
함정과 경계 사례
대부분의 버그는 배열 하나의 요소가 바닥나거나 값을 비교하는 방식에서 발생합니다.
- 배열 하나를 모두 사용하자마자 반복문을 멈추고 다른 배열의 나머지 요소를 잊어버리는 경우입니다.
[1, 2, 3]과[4, 5, 6]이 있으면 반복문은 1, 2, 3을 처리한 뒤 끝나며, 4, 5, 6도 여전히 복사해야 합니다. i가 끝에 도달한 뒤에nums1[i]를 읽는 경우입니다. 비교하기 전에 두 인덱스가 모두 범위 안에 있는지 확인하세요.- 중복 항목을 누락하는 경우입니다.
[0, 0]과[0]을 병합하면[0, 0, 0]이 되며,[0]이 되지 않습니다. - JavaScript와 TypeScript에서는 비교 함수를 지정하지 않고
sort()를 호출하면 숫자를 텍스트로 정렬하므로,[-5, 10, 9]는[-5, 10, 9]로 정렬됩니다.(a, b) => a - b를 전달하세요. - Lua와 R에서는 배열의 인덱스가 1부터 시작하므로 두 인덱스 모두 1부터 시작하고, 범위 검사에는
<=를 사용합니다.
자주 묻는 질문4
정렬된 두 배열을 병합하는 시간 복잡도는 얼마인가요?
두 포인터를 사용하면 O(m + n)이며, 여기서 m과 n은 두 배열의 길이입니다. 각 단계에서 값 하나를 배치하고, 어떤 값도 두 번 살펴보지 않습니다. 대신 이어 붙인 뒤 정렬하면 O((m + n) log(m + n))의 비용이 듭니다.
정렬된 두 배열을 제자리에서 어떻게 병합하나요?
첫 번째 배열의 끝에 두 배열의 원소를 모두 담을 공간이 있으면, 뒤에서부터 채우세요. 두 배열에 남아 있는 가장 큰 값을 비교하고, 더 큰 값을 마지막 빈 위치에 쓴 다음 왼쪽으로 이동하세요. 뒤에서부터 쓰면 아직 제자리에 놓지 않은 첫 번째 배열의 값을 덮어쓰지 않으므로, 두 번째 배열이 필요하지 않습니다.
정렬된 두 배열을 병합하는 것은 병합 정렬의 병합 단계와 같은가요?
맞습니다. 병합 정렬은 배열을 절반으로 나누고, 각 절반을 정렬한 다음, 정확히 이 투 포인터 루프로 정렬된 두 절반을 합칩니다. 값이 같을 때 왼쪽 값을 선택하면 같은 값들이 원래 순서를 유지하므로 병합 정렬은 안정 정렬이 됩니다.
배열을 연결한 다음 sort를 호출하면 안 되나요?
올바른 답을 제공하며, 실제로는 빠른 경우가 많습니다. 하지만 입력이 이미 정렬되어 있다는 점을 무시하고 추가로 log만큼의 비용이 듭니다. 면접에서는 두 포인터 병합이 기대되는 답변인데, 주어진 순서를 활용할 수 있음을 보여 주기 때문입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def merge(nums1, nums2):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
기대값
[1, 2, 3, 4, 9, 10]