정렬 (Sort)
정렬에 대해 이어서 알아보았다.
LeetCode 148.Sort List
연결 리스트를 O(n log n)에 정렬하라.
Solution 1 병합 정렬
이 문제는 시간 복잡도 O(n log n)로 제한 시간을 줬기 때문에 버블 정렬과 같은 알고리즘은 사용할 수 없다. 병합 정렬이나 퀵 정렬을 이용해야 하는데 병합 정렬로 먼저 작성해본다.
병합 정렬의 분할 정복을 위해서는 중앙을 분할해야 하는데 연결 리스트의 경우 전체 길이를 알 수 없기 때문에 다음과 같이 런너 기법을 활용해야 한다.
half, slow, fast = None, head, head
while fast and fast.next:
half, slow, fast = slow, slow.next, fast.next.next
half.next = Nonehalf, slow, fast 3개의 변수를 만들어 두고 slow는 한칸씩, fast는 두칸씩 앞으로 이동시킨다. 이렇게 하면 fast가 끝에 도달했을 때에 slow가 중앙에 도착해있게 된다. half는 slow의 바로 이전 값으로 하고 마지막 half.next = None으로 half 위치를 기주으로 연결 리스트 관계를 끊어버린다. 이제 다음과 같이 분할해서 재귀 호출을 진행해본다.
def sortList(self, head: ListNode) -> ListNode:
...
l1 = self.sortList(head)
l2 = self.sortList(slow)head는 시작 노드이고, slow는 위락 탐색을 통해 발견한 중항 지점이다. slow를 기준으로 계속 재귀 호출을 해나가면 결국 연결 리스트는 단일 아이템으로 모두 쪼개진다.
def sortList(self, head: ListNode) -> ListNode:
...
return self.mergeTowLists(l1, l2)이처럼 마지막에는 최종적으로 쪼갰던 아이템을 다시 합쳐서 반환해야 한다. 그냥 합치는 것이 아니라 다음처럼 크기 비교를 통해 정렬하면서 이어 붙인다.
def mergeTwoLists(self, l1:ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val:
l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2mergeTwoLists() 메소드는 연결 리스트를 입력값으로 받아, 길이가 얼마가 되든 재귀 호출을 통해 l1의 포인터를 이동하면서 정렬해 반환한다. 여기서 return l1 or l2는 l1에 값이 있을 경우 l1을 반환하고, l1이 None일 경우 l2를 반환한다. 즉 l1이 우선이다. 이는 다음을 통해 확인할 수 있다.
>>> 1 or None
1
>>> 1 or 2
1
>>> None or 2
2전체 코드는 다음과 같이 작성할 수 있다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode)->ListNode:
if l1 and l2:
if l1.val>l2.val:
l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not (head and head.next):
return head
half, slow, fast=None, head, head
while fast and fast.next:
half, slow, fast=slow, slow.next, fast.next.next
half.next=None
l1 = self.sortList(head)
l2 = self.sortList(slow)
return self.mergeTwoLists(l1, l2)
Solution 2 퀵 정렬
이 문제는 퀵 정렬을 이용해서도 풀 수 있다. 그러나 로무토 파티션 등의 일반적인 퀵 정렬 알고리즘으로 구현하는 경우 타임 아웃이 발생한다. 1, 2, 3 단 3개의 아이템으로 구성된 1,000개 입력값으로 이뤄진 테스트 케이스가 있는데, 이 부분에서 파이썬의 퀵 정렬은 계속 타임 아웃을 발생시킨다. 퀵 정렬은 대표적인 불안정 정렬로 같은 값이 반복될 경우에도 계속해서 스왑을 시도한다. 연결 리스트는 특성상 피벗을 임의로 지정하기가 어렵기 때문에 여기서는 피벗을 항상 첫번째 값으로 설정하였는데, 이 경우 이미 정렬된 리스트가 입력값으로 들어오게 되면 계속해서 불균형 리스트로 나뉘기 때문에 최악의 결과가 나타나게 된다.
퀵 정렬은 임력값에 따라 성능의 편차가 크고 다루기가 까다롭기 때문에 성능이 우수함에도 실무에서는 좀처럼 퀵 정렬을 사용하지 않는다. 이 문제 또한 퀵 정렬로 풀이하기가 어렵다.
Solution 3 내장 함수를 이용하는 실용적인 방법
이 문제는 사실 정렬을 직접 구현할 필요가 없다. 요즘 대부분의 프로그래밍 언어에는 표준 라이브러리에 이미 성능 좋은 정렬 알고리즘을 제공하고 있기 때문이다. 파이썬에서도 .sort(), sorted()와 같은 정렬 알고리즘이 정의되어 있다. C를 이용한 팀소트 구현이기 때문에 매우 성능이 좋다는 것도 앞서 알아본 바가 있다. 실행시간을 조금이라도 더 줄여야 하는 코딩 테스트에서는 가장 현명한 접근 방식이기도 하며, 실무에서도 당연히 이 같은 방식으로 풀이하는 편이 훨씬 실용적이다.
화이트보드에 알고리즘을 작성해야 하는 면접이라면 이런 방식 대신, 퀵 정렬의 단점을 설명하며 이 상황에서 사용하기 어려운 이유를 설명한 후, Solution 1의 병합 정렬을 설명하는 편이 가장 좋다. 병합 정렬을 설명한 뒤에 실무에서는 sort() 함수를 사용하겠다는 점을 어필하는 것도 좋은 방법이다.
내장 함수를 이용하는 실용적인 풀이를 한번 보면 다음과 같이 연결 리스트를 파이썬의 리스트로 변환해줘야 한다.
lst: List = []
while p:
lst.append(p.val)
p=p.next그 후, 파이썬의 내장 정렬 함수인 sort()를 다음과 같이 적용한다.
lst.sort()정렬한 리스트는 다음과 같이 다시 연결 리스트로 변환해준다.
p=head
for i in range(len(lst)):
p.val=lst[i]
p=p.next
return head여기서 p는 포인터이다. 연결 리스트를 순회하기 위한 포인터 변수를 p로 설정했고, 순회하며 값을 채워넣는 역할을 한다. 그런 다음 루트 노트 head를 반환한다. 전체 코드는 다음과 같다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
p=head
lst: List=[]
while p:
lst.append(p.val)
p=p.next
lst.sort()
p=head
for i in range(len(lst)):
p.val=lst[i]
p=p.next
return head
단순하고 직관적이고 쉽지만 이전에 사용한 병합 정렬 풀이보다 훨씬 빠르게 해결되는 것을 볼 수 있다. 놀라운 점은 연결 리스트를 리스트로 변경하는 과정이 추가되었음에도 이 방식이 가장 빠르다는 점이다. 이처럼 실무에서나 코딩 테스트 시에 내장 함수를 잘 활용하면 매우 효율적이기 때문에, 별도의 제약 사항이 없다면 잘 활용할 필요가 있다.
LeetCode 56.Merge Intervals
겹치는 구간을 병합하라.
Solution 1 정렬하여 병합
이 문제를 풀기 위해서는 가장 먼저 첫번째 원소에 대한 오름차순 정렬을 적용해야 한다.
sorted(intervals, key=lambda x: x[0])그리고 현재 아이템의 시작이 이전 아이템의 끝과 겹치게 되면 최댓값을 기준으로 병합하는 형태로 계속 반복해 나간다. 만약 다음 아이템의 시작 값이 이전 아이템의 끝과 더 이상 겹치지 않게 되면다면, 병합을 멈추고 다음과 같이 merged += i,를 이용해 새로운 아이템을 추가한다. 전체 코드는 다음과 같다.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
merged=[]
for i in sorted(intervals, key=lambda x:x[0]):
if merged and i[0]<=merged[-1][1]:
merged[-1][1]=max(merged[-1][1], i[1])
else:
merged+=i,
return merged
문법: 콤마(,) 연산자
이 풀이에는 특이한 문법이 등장한다.
merged += i,이렇게 연산자와 변수 뒤에 콤마(,)가 붙으면 어떠한 동작을 할까? 우선 기본적인 추가 연산은 다음과 같다.
>>> a = [1]
>>> b = [2, 3]
>>> a += b
>>> a
[1, 2, 3]단순히 +=를 했을 때에는 요소를 이어붙인다. 행렬의 연결 연산과 동일하다. 이번에는 콤마를 붙인다.
>>> a = [1]
>>> b = [2, 3]
>>> a += b,
>>> a
[1, [2, 3]]이렇게 중첩 리스트가 된다. 콤마는 중첩 리스트로 만들어주는 역할을 하며, 대괄호 []를 부여한 것과 같은 역할을 한다.
>>> a += [b]
>>> a
[1, [2, 3]]콤마나 대괄호 둘 중 편한 방식을 사용하면 된다.
LeetCode 147.Insertion Sort List
연결 리스트를 삽입 정렬로 정렬하라.
Solution 1 삽입 정렬
이 문제는 삽입 정렬을 사용하도록 제시한 문제이다. 4->2->1->3이 입력값으로 들어왔을 때에, 삽입 정렬은 다음과 같은 과정을 거친다.
None -> 4 -> 2 -> 1 -> 3
cur head ----------->
None 4 -> 2 -> 1 -> 3
None -> 4 2 -> 1 -> 3
None -> 2 -> 4 1 -> 3
None -> 1 -> 2 -> 4 3
2 -> 3 -> 4 None
None -> 1 -> 2 -> 3 -> 4 None먼저 삽입 정렬은 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠 진행한다. head는 정렬을 해야 할 대상이며, cur는 정렬을 끝낸 대상으로 정한다. 다음과 같이 정렬을 해야 할 대상 head를 반복한다.
cur = parent = ListNode(None)
while head:
while cur.next and cur.next.val < head.val:
cur = cur.next먼저, cur와 parent는 빈 노드로 정한다. cur에는 정렬을 끝낸 연결 리스트를 추가해줄 것이고, parent는 계속 그 위치에 두어 사실상 루트를 가리키게 한다. 정렬을 끝낸 cur는 이미 정렬된 상태이므로, 정렬을 해야 할 대상 head와 비교하면서 더 작다면 계속 cur.next를 이용해 다음으로 이동한다. 이제 정렬이 필요한 위치, 즉 cur에 삽입될 위치를 찾았다면 다음과 같이 cur 연결 리스트에 추가한다.
cur.next, head.next, head = head, cur.next, head.next
cur=parent찾은 cur 위치 다음에 head가 들어가고, head.next에는 cur.next를 연결해 계속 이어지게 한다. 그리고 다음번 head는 head.next로 차례를 이어받는다. 이후에는 cur=parent를 통해 다시 처음으로 되돌아가며, 차례대로 다시 비교하게 된다. 위에서 cur의 마지막 노드가 2->3->4 형태가 되는데, 이는 입력값에서 유일하게 그 직전 값인 1보다 head의 값인 3이 더 크기 때문이다. 따라서 cur=cur.next로 작거나 같아질 때까지 계속 전진한다. 이후에 head는 None이 되면서 비교가 끝난다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur=parent=ListNode(None)
while head:
while cur.next and cur.next.val<head.val:
cur=cur.next
cur.next, head.next, head = head, cur.next, head.next
cur=parent
return cur.next
이 풀이는 보기에는 깔끔하지만 실행 시간이 2초를 넘겼다. 더 최적화된 방법이 다음 풀이에 있다.
Solution 2 삽입 정렬의 비교 조건 개선
삽입 정렬은 정답 셋과 정답이 아닌 셋을 비교할 때, 정답 셋의 가장 큰 값부터 왼쪽 방향으로 내려가며 스왑되는 위치를 찾는다. 그러나 이 문제의 경우 연결 리스트이고, 이중 연결 리스트도 아니기 때문에 큰 값에서부터 작은 값까지 거꾸로 거슬러 내려가는 것이 사실상 불가능하다. 그러다보니 매번 가장 작은 값부터 차례대로 크기 비교를 하는 매우 비효율적인 연산이 수행된다. Solution 1이 2초나 걸린 이유도 여기에 있다.
Solution 1에 있는 다음과 같은 코드를 개선하면 효율성을 높일 수 있다.
cur=parent다음번 head를 비교할 때 정렬된 노드인 cur도 다시 맨 처음으로 되돌아가라는 명령이다. 만약 다음번 head도 cur보다 큰 상태라면 굳이 돌아갈 필요가 없다. 되돌아가지 않고 그 상태에서 계속 비교를 할 수 있다면 비교 횟수를 획기적으로 줄일 수 있다. 거꾸로 비교할 수 없는 대신, 필요한 때만 돌아가는 형태로 개선할 수 있고, 되돌아가는 경우는 cur이 head보다 클 때만 적용하면 된다. cur=parent 앞에 조건문을 추가해 다음과 같이 수정하였다.
if head and cur.val > head.val:
cur=parent전체 코드는 다음과 같다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur=parent=ListNode(0)
while head:
while cur.next and cur.next.val<head.val:
cur=cur.next
cur.next, head.next, head = head, cur.next, head.next
if head and cur.val > head.val:
cur=parent
return parent.nextcur.val을 비교할 때 None 타입이면 에러가 발생하므로 초기 값을 0으로 수정하였다.
단 한줄의 조건문으로 성능이 10배 이상 향상되었다.
