Python에서 두 개의 정렬된 목록 병합

1. Python에서 두 개의 정렬된 목록 병합
2. Python에서 두 개의 정렬된 목록을 병합하기 위한 순진한 접근 방식
3. Python에서 heapq.merge() 메서드를 사용하여 두 개의 정렬된 목록 병합
4. Python에서 sorted() 함수를 사용하여 두 개의 정렬된 목록 병합
5. 결론

정렬된 목록은 오름차순 또는 내림차순으로 정렬된 목록이며 이러한 정렬된 목록을 병합한다는 것은 정렬된 상태를 유지하는 방식으로 두 목록을 결합하는 것을 의미합니다.

Python에는 두 개의 정렬된 목록을 병합할 수 있는 다양한 방법이 있습니다. Python에는 이 작업을 수행하기 위한 내장 함수가 있지만 이러한 내장 함수를 설계하는 데 사용되는 순진한 접근 방식도 논의할 것입니다.

Python에서 두 개의 정렬된 목록 병합

이 기사에서 우리는 문제 설명을 받았고 동일한 문제에 대한 솔루션을 설계하라는 요청을 받았습니다. 문제는 개별적으로 정렬된 두 개의 목록이 있지만 병합된 후에도 정렬된 상태를 유지하려면 병합해야 한다는 것입니다.

예를 들어 이해해 봅시다.

list1 = [2, 5, 7, 8, 9]
list2 = [0, 1, 3, 4, 6]

출력:

Sorted List: [0,1,2,3,4,5,6,7,8,9]

출력의 정렬된 목록은 list1 및 list2 목록의 요소로 구성됩니다. 병합된 후에는 결합된 목록이 여전히 정렬되도록 정렬됩니다.

이 문제는 병합 정렬에서 사용되는 merge 기능을 설계하는 것과 동일합니다. 따라서 이러한 질문을 해결하는 동안 이러한 유형의 문제에 자주 직면합니다.

그러므로 우리는 그것에 접근하는 방법에 대한 기본적인 생각을 가지고 있어야 합니다. 이제 이 문제를 어떻게 해결할 것인지 이해해 봅시다.

Python에서 두 개의 정렬된 목록을 병합하기 위한 순진한 접근 방식

우리가 논의할 솔루션은 Python에서 두 개의 정렬된 목록을 병합하는 순진한 접근 방식입니다. 이 접근 방식에서는 두 목록을 동시에 순회하고 현재 위치에서 두 요소 사이의 더 작은 요소를 확인합니다.

더 작은 요소가 답변에 추가됩니다. 그러나 두 목록 중 하나가 완전히 순회되면 병합된 요소 뒤에 다른 목록이 결과에 추가됩니다.

더 잘 이해하기 위해 코드를 살펴보겠습니다.

firstList = [2, 7, 8, 9]
secondList = [0, 1, 4, 6]
result = []
i, j = 0, 0

while i < len(firstList) and j < len(secondList):
    if firstList[i] < secondList[j]:
        result.append(firstList[i])
        i = i + 1
    else:
        result.append(secondList[j])
        j = j + 1

result = result + firstList[i:] + secondList[j:]
print("Sorted List: " + str(result))

출력:

Sorted List: [0, 1, 2, 4, 6, 7, 8, 9]

우리는 병합된 목록을 저장할 위의 코드에서 빈 목록 result를 선언했습니다. 그런 다음 두 목록 중 하나 또는 둘 다 소진될 때까지 두 목록을 반복했습니다.

루프 내에서 두 목록의 요소를 비교하고 더 작은 요소를 result 변수에 추가한 다음 현재 인덱스를 1씩 증가시킵니다.

목록 중 하나에 결과에 포함되지 않은 요소가 있는 경우 Python의 슬라이싱 연산자를 사용하여 나머지 요소를 답변에 병합합니다.

이 접근 방식에서는 목록을 한 번만 반복했습니다. 따라서 O(n1+n2)의 시간 복잡도를 갖는 반면 위의 접근 방식에 대한 공간 복잡도는 O(n1+n2)입니다. 여기서 n1 및 n2는 정렬된 크기를 나타냅니다. 기울기.

Python에서 heapq.merge() 메서드를 사용하여 두 개의 정렬된 목록 병합

Python의 heapq 모듈은 힙 큐를 참조합니다. 하지만 이 모듈인 Heapq는 Python에서 우선 순위 큐를 구현하는 데 주로 사용됩니다.

heapq 모듈에는 Python의 merge() 함수가 포함되어 있습니다. 이 함수는 정렬된 여러 목록을 인수로 사용하고 하나의 결합된 병합된 목록을 반환합니다.

Python에서 heapq.merge() 함수를 사용하여 병합 작업을 수행하는 방법을 살펴보겠습니다.

from heapq import merge

first = [2, 7, 8, 9]
second = [0, 1, 4, 6]

res = list(merge(first, second))

print("Merged Sorted list: ", str(res))

출력:

Merged Sorted list:  [0, 1, 2, 4, 6, 7, 8, 9]

위의 코드에서 merge() 함수의 두 개의 정렬된 목록 first 및 second를 인수로 전달한 후 명시적으로 목록으로 변환합니다. 결과적으로 병합된 정렬 목록은 ans 변수에 저장됩니다.

보시다시피 heapq 모듈의 merge() 기능을 사용하여 Python에서 두 개의 정렬된 목록을 병합할 수 있습니다.

Python에서 sorted() 함수를 사용하여 두 개의 정렬된 목록 병합

Python의 sorted() 함수는 매개변수로 제공된 목록 또는 튜플을 정렬합니다. 원래 시퀀스를 변경하지 않고 정렬될 목록을 항상 반환합니다.

이 함수를 사용하여 단 한 줄로 문제를 해결할 수 있습니다. 두 목록을 함께 추가한 다음 sorted() 함수를 결과 목록에 적용합니다.

예를 들어 이해해 봅시다.

first = [2, 7, 9]
second = [0, 1, 4]

result = sorted(first + second)

print("List after sorting: ", str(result))

출력:

List after sorting:  [0, 1, 2, 4, 7, 9]

위의 프로그램에서 + 연산자를 사용하여 두 목록을 함께 추가했습니다. 연결 연산자 +는 코드에 입력된 순서대로 여러 목록을 하나의 결합된 목록에 추가하는 데 사용됩니다.

그런 다음 추가된 목록에 sorted() 함수를 적용하여 시퀀스를 정렬하고 결과를 인쇄합니다.

이 접근 방식은 내부적으로 두 목록을 하나의 목록에 추가하므로 위에서 설명한 다른 두 접근 방식보다 더 많은 시간이 소요되기 때문에 시간이 더 걸릴 수 있습니다.

결론

이 기사에서는 Python에서 두 개의 정렬된 목록을 병합할 수 있는 다양한 접근 방식에 대해 설명합니다. 그 중 두 개는 파이썬에 내장된 방법이고 다른 하나는 문제에 대한 자세한 접근 방식입니다.

sorted() 함수는 추가된 목록을 정렬하는 데 사용되는 내장 함수 중 하나인 반면 다른 heapq.merge()는 Python에서 두 개의 정렬된 목록을 병합하는 데 사용되는 메서드입니다. 두 기능 모두 한 줄에서 작업을 수행할 수 있습니다.

자세한 접근 방식은 목록을 반복하고 현재 인덱스의 각 요소를 비교하고 응답에 더 작은 요소를 추가한 다음 현재 인덱스를 1씩 증가시키는 것입니다. 이 루프는 목록 중 하나 또는 둘 다 소진될 때까지 실행되며 그 후에 나머지 요소는 Python의 슬라이싱 연산자를 통해 추가됩니다.

위에서 설명한 방법 중 하나를 사용하여 문제를 해결할 수 있습니다.