연결 리스트(linked list)가 하나 있다고 가정해 보겠습니다. 이 리스트를 오름차순으로 정렬해야 합니다.
예를 들어 입력이 [5, 8, 4, 1, 5, 6, 3]이라면 출력은 [1, 3, 4, 5, 5, 6, 8]이 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- values라는 새로운 빈 리스트를 생성합니다.
- head 변수에 현재 노드(node)를 저장합니다.
- node가 null이 아닐 때까지 반복합니다.
- 노드의 값을 values 리스트의 끝에 추가합니다.
- node를 다음 노드로 이동시킵니다.
- values 리스트를 정렬합니다.
- 정렬된 values의 요소들로 데크(deque)를 생성합니다.
- node를 다시 head로 설정합니다.
- node가 null이 아닐 때까지 반복합니다.
- 큐의 왼쪽 요소를 꺼내어(popleft) 해당 노드의 값에 대입합니다.
- node를 다음 노드로 이동시킵니다.
- head를 반환합니다.
동작 원리와 시간 복잡도
이 방법은 연결 리스트의 모든 값을 일반 파이썬 리스트로 옮긴 뒤, 내장 정렬 함수인 sort()를 활용하는 전략입니다. 정렬이 완료되면 collections.deque를 사용하여 앞쪽부터 효율적으로 값을 꺼내고, 원래 연결 리스트의 각 노드에 순서대로 다시 대입합니다.
전체 수행 시간은 정렬 과정이 지배하므로 시간 복잡도는 O(n log n)입니다. 또한 값을 임시로 담아 둘 추가 리스트가 필요하기 때문에 공간 복잡도는 O(n)입니다.
예제 코드
import collections
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, node):
values = []
head = node
while node:
values.append(node.val)
node = node.next
values.sort()
values = collections.deque(values)
node = head
while node:
node.val = values.popleft()
node = node.next
return head
ob = Solution()
head = make_list([5, 8, 4, 1, 5, 6, 3])
print_list(ob.solve(head))입력
[5, 8, 4, 1, 5, 6, 3]
출력
[1, 3, 4, 5, 5, 6, 8]