[19일차] TIL (Quick Sort)

퀵정렬

맨 뒤의 값을 pivot값으로 정하고 pivot값보다 작은 값은 앞으로 보내고 큰값은 그대로 둔 후 pivot값을 그 사이에 위치시켜 두 부분으로 나누어 재귀적으로 정렬하는 방식입니다.

 

시간복잡도는 O(NlogN)이지만 최악의 경우 시간복잡도가 심각하게 늘어날 수 있습니다.

 

다음은 정렬과 관련된 문제들을 풀어본 후 회고해보겠습니다.

1. 리스트 정렬

https://leetcode.com/problems/sort-list/

링크드 리스트 문제를 만나면 아직 접근이 힘든 부분이 있습니다. 연결리스트를 처음부터 구현하는것 부터 다시 복습해야할 것 같습니다.

# 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]:
        list_nums = []
        
        while head != None:
            list_nums.append(head.val)
            head = head.next
            
        list_nums.sort()
        
        answerList = ListNode(0)
        
        result = answerList
        
        for num in list_nums:
            answerList.next = ListNode(num)
            answerList = answerList.next
            
        return result.next

 

 

2. 색 정렬

https://leetcode.com/problems/sort-colors/submissions/

 

문제에서 sort 메서드를 사용하지 말라고 조건을 정했습니다. 따라서 정렬을 직접 구현해서 풀어야하는데 저는 오늘 공부한 quicksort를 이용해 풀이해 보겠습니다. 풀이는 다음과 같습니다.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def quicksort(lst, start, end):
            def partition(part, ps, pe):
                pivot = part[pe]
                i = ps - 1
                for j in range(ps, pe):
                    if part[j] <= pivot:
                        i += 1
                        part[i], part[j] = part[j], part[i]
                        
                part[i + 1], part[pe] = part[pe], part[i + 1]
                return i + 1
            
            
            if start >= end:
                return None

            p = partition(lst, start, end)
            quicksort(lst, start, p - 1)
            quicksort(lst, p + 1, end)
            return nums
        

        quicksort(nums, 0, len(nums) - 1)

 

3. 좌표 정렬하기

https://www.acmicpc.net/problem/11650

 

파이썬의 lambda를 사용하면 간단하게 정렬할 수 있습니다.

우선 좌표 값이 추가되거나 바뀔 일이 없으므로 튜플형태로 lst라는 배열에 추가합니다.

새로운 배열에 첫 번째 인덱스의 값으로 우선적으로 정렬하고 두 번째 인덱스의 값을 그 다음 우선순위로 정렬하고 하나씩 출력합니다.

n = int(input())

lst = []
for _ in range(n):
    x, y = map(int, input().split())
    lst.append((x, y))

new_lst = sorted(lst, key=lambda x: (x[0], x[1]))

for a, b in new_lst:
    print(a, b)

 

4. 좌표 정렬하기2

https://www.acmicpc.net/problem/11651

위 문제와 다른 점은 두 번째 인덱스의 값을 우선적으로 정렬하고 같은 경우 첫 번째 인덱스의 값을 비교하여 정렬한다는 점입니다.

코드는 다음과 같습니다.

n = int(input())

lst = []
for _ in range(n):
    x, y = map(int, input().split())
    lst.append((x, y))

new_lst = sorted(lst, key=lambda x: (x[1], x[0]))

for a, b in new_lst:
    print(a, b)

 

 

5. 국영수

https://www.acmicpc.net/problem/10825

튜플의 각 원소마다 오름차순인지 내림차순인지 구분해서 정렬하는게 문제였습니다. 찾아보니 lambda에 음수기호를 붙이는 것만으로도 오름차순을 내림차순으로 reverse할 수 있다는 것을 찾았습니다. 다음은 적용 코드입니다.

n = int(input())

lst = []
for _ in range(n):
    name, k, e, m = input().split()
    lst.append((name, int(k), int(e), int(m)))


new_lst = sorted(lst, key=lambda x: (-x[1], x[2], -x[3], x[0]))

for s in new_lst:
    print(s[0])

 

6. 안테나

https://www.acmicpc.net/problem/18310

 

알고리즘 자체는 생각보다 간단한데 떠올리는게 쉽지 않은 문제였습니다. 완전 탐색을 떠올렸지만 중앙값 인덱스의 집을 반환해주면 되는 문제였습니다. 

n = int(input())
home_list = list(map(int, input().split()))

home_list.sort()
# 1, 5, 7, 9

print(home_list[(n - 1) // 2])