Merge Two Sorted Lists

Q: 정렬된 두 리스트를 병합하는 데 걸리는 시간 복잡도는 얼마인가요?

O(L1 + L2) 입니다. 각 비교에서 노드 하나를 배치하며, 어떤 노드도 두 번 배치되지 않습니다. 노드 객체를 사용하면 병합은 링크만 변경하므로 추가 메모리가 O(1) 필요합니다. 여기서 사용한 배열의 경우 공유 링크 배열에 O(L1 + L2) 의 메모리가 필요합니다.

쉬움연결 리스트 투 포인터

+10

두 개의 단일 연결 리스트가 주어지며, 각 리스트는 길이가 같은 두 배열에 저장되어 있습니다. 첫 번째 리스트에서 노드 i는 값 values1[i]을 가지며 노드 next1[i]를 가리킵니다. 두 번째 리스트도 next2와 values2를 사용해 같은 방식으로 구성됩니다. 두 리스트 모두 -1이 리스트의 끝을 나타내고, 헤드는 노드 0입니다. 노드가 리스트 순서대로 저장되어 있지 않으므로 링크를 따라가세요.

각 리스트는 링크를 따라갈 때 비내림차순으로 정렬되어 있습니다. 두 리스트를 하나의 정렬된 리스트로 병합하고, 그 값을 순서대로 반환하세요.

함수

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: 첫 번째 목록의 각 노드가 연결되는 노드의 인덱스 또는 마지막 노드의 경우 -1
values1integer-array: 첫 번째 목록의 각 노드가 보유한 값
next2integer-array: 두 번째 리스트의 각 노드가 연결되는 노드의 인덱스, 또는 마지막 노드의 경우 -1
values2integer-array: 두 번째 리스트의 각 노드가 보유한 값
반환값integer-array: 병합된 목록의 값을 순서대로

제약 조건

1 ≤ L1 ≤ 2000이며, 여기서 L1은 next1과 values1의 길이입니다.
1 ≤ L2 ≤ 2000이며, 여기서 L2는 next2와 values2의 길이입니다.
-1000 ≤ values1[i], values2[j] ≤ 1000
각 next1의 항목은 -1이거나 첫 번째 리스트의 노드 인덱스이고, next2의 각 항목은 -1이거나 두 번째 리스트의 노드 인덱스입니다.
노드 0에서 시작하여 각 리스트는 모든 노드를 정확히 한 번씩 방문한 다음 -1에 도달합니다. 순환은 없습니다.
각 리스트는 연결을 따라 비감소 순서로 정렬되어 있습니다.

예제

입력: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
출력: [1, 2, 3, 4, 6, 7, 9]
설명: 링크를 따라가면 첫 번째 목록은 노드 0, 2, 1을 방문하고 1, 4, 6을 읽습니다. 두 번째 목록은 2, 3, 7, 9를 읽습니다. 매번 앞에 있는 값 중 더 작은 값을 선택하면 1, 2, 3, 4, 6, 7, 9가 됩니다.

입력: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
출력: [-3, 0, 0, 5]
설명: 첫 번째 목록은 -3, 0, 5이고 두 번째 목록은 단일 값 0입니다. 두 0 모두 결과에 남으므로 결과에는 값이 네 개 있습니다.

입력: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
출력: [1, 2, 3, 8, 10]
설명: 두 번째 목록은 1, 2, 3이며, 모두 첫 번째 목록을 시작하는 8보다 작습니다. 두 번째 목록 전체가 먼저 나오고, 그다음에 8, 10이 나옵니다.

후속 질문

총 노드 수가 N일 때, O(N log k) 시간에 k개의 정렬된 리스트를 병합할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

두 리스트는 모두 정렬되어 있으므로, 남은 값 중 가장 작은 값은 항상 둘 중 한 리스트의 맨 앞에 있습니다. 두 맨 앞 값을 비교하고, 더 작은 값을 결과에 연결한 다음 해당 리스트에서 한 칸 앞으로 이동합니다. N = L1 + L2개의 값을 모두 정렬해도 되지만, 그렇게 하면 이 순서를 활용하지 못하고 O(N log N)의 비용이 듭니다.

모든 값을 하나의 배열에 넣고 정렬하세요

핵심 아이디어

병합된 목록은 모든 N 값의 정렬된 버전이므로, 두 값 배열을 하나로 합쳐 정렬하세요. 배열 안에서 노드의 순서는 중요하지 않습니다. 정렬 과정에서 모든 값이 제자리를 찾기 때문입니다. N ≤ 4000이면 충분히 빠르지만, 정렬에는 O(N log N)번의 비교가 필요합니다. 반면 병합에는 최대 N-1번의 비교만 필요하며, 정렬은 링크를 전혀 건드리지 않습니다. 이 문제는 바로 그 기술을 평가합니다.

알고리즘

values1과 values2를 하나의 배열에 복사합니다.
배열을 비내림차순으로 정렬합니다.
반환합니다.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

더미 헤드 뒤에 노드들을 연결하세요

핵심 아이디어

여기서 포인터는 노드 인덱스입니다. 두 리스트의 노드를 하나의 연결 체인으로 합치려면 번호를 하나로 통일합니다. 리스트 2의 노드 j는 노드 L1+j가 되고, 연결도 같은 방식으로 이동합니다. 번호가 L1+L2인 더미 노드는 결과의 맨 앞에 놓입니다.

a와 b는 각 리스트에서 아직 사용하지 않은 첫 번째 노드를 가리키게 하고, tail은 병합된 체인의 끝을 가리키게 합니다. 매 단계에서 tail을 더 작은 쪽의 앞 노드에 연결하고, 그 포인터와 tail을 앞으로 이동합니다. 한 리스트가 소진되면 다른 리스트의 나머지 부분은 이미 정렬되어 연결된 상태이므로, 한 번의 대입으로 이를 연결할 수 있습니다. 첫 번째 예시에서 리스트 2는 노드 3부터 6까지가 됩니다. 노드 0, 3, 6, 2, 1을 거친 뒤 리스트 1은 비어 있고, link[tail] = 4로 7, 9를 연결합니다.

각 노드는 최대 한 번 연결됩니다. 시간 복잡도는 O(N)입니다. 공유 링크 배열에는 O(N)의 메모리가 필요하지만, 노드 객체를 사용하면 메모리가 필요하지 않습니다.

알고리즘

링크 배열 하나를 만듭니다. next1을 넣고, L1만큼 이동한 next2를 넣습니다(-1은 그대로 둡니다). 그런 다음 더미 L1+L2에 -1을 넣습니다. 이에 대응하는 값 배열도 만듭니다.
a = 0, b = L1로 설정하고 tail은 더미를 가리키도록 설정합니다.
a와 b가 모두 -1이 아닐 동안, 더 작은 쪽(같으면 a)에 tail을 연결하고, 해당 포인터를 이동한 다음 tail을 그 위치로 옮깁니다.
a와 b 중 -1이 아닌 쪽에 tail을 연결합니다.
link[dummy]에서 시작해 -1까지 순회하며 값들을 모읍니다.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

함정과 경계 사례

인덱스 순서대로 배열을 병합하는 것. 노드가 섞인 순서로 저장되어 있으므로 values1 자체는 정렬되어 있지 않습니다. 첫 번째 예에서는 [1, 6, 4]입니다. 노드 0에서 시작해 따라가는 경로만 정렬되어 있습니다.
남은 항목을 잊는 것. 한쪽 목록이 끝나면 루프가 멈추는데, 다른 목록의 나머지를 버리면 가장 큰 값인 첫 번째 예의 7, 9를 잃게 됩니다.
잘못된 포인터를 이동하거나 둘 다 이동하는 것. 노드를 가져온 목록의 포인터만 앞으로 이동합니다.
두 인덱스 체계를 혼동하는 것. 목록 2의 노드 2는 목록 1의 노드 2가 아닙니다. 목록 2의 인덱스와 링크에 L1을 더하고, -1은 그대로 둡니다.

자주 묻는 질문3

정렬된 두 리스트를 병합하는 데 걸리는 시간 복잡도는 얼마인가요?

O(L1 + L2)입니다. 각 비교에서 노드 하나를 배치하며, 어떤 노드도 두 번 배치되지 않습니다. 노드 객체를 사용하면 병합은 링크만 변경하므로 추가 메모리가 O(1) 필요합니다. 여기서 사용한 배열의 경우 공유 링크 배열에 O(L1 + L2)의 메모리가 필요합니다.

연결 리스트를 병합할 때 더미 노드를 사용하는 이유는 무엇인가요?

그것이 없으면 결과의 첫 번째 노드는 아직 그 뒤에 연결할 꼬리가 없으므로 별도의 코드가 필요합니다. 더미는 자리 표시자 헤드이므로 첫 번째 노드도 다른 노드와 같은 방식으로 연결됩니다. 마지막에는 더미의 next 노드를 반환하고 자리 표시자는 사라집니다.

정렬된 두 리스트를 재귀적으로 병합해야 할까요, 아니면 반복적으로 병합해야 할까요?

재귀 버전은 짧습니다. 더 작은 헤드가 나머지 모든 요소를 병합한 결과에 연결됩니다. 하지만 노드마다 스택 프레임을 하나씩 사용하므로, 일부 언어에서는 노드가 몇천 개 있는 리스트가 스택 오버플로를 일으킬 수 있습니다. 꼬리 포인터를 사용하는 반복 루프는 동일한 작업을 일정한 스택 공간에서 수행합니다.

def mergeTwoLists(next1, values1, next2, values2):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

예상 출력

[1, 2, 3, 4, 6, 7, 9]