[5부 알고리즘] 17장 정렬

📌 58) 리스트 정렬 ( 리트코드 148. Sort List )

✔ 풀이1 (병합 정렬)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTowList(self, l1, l2):
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTowList(l1.next, l2)
        
        return l1 or l2 #둘 다 값이 있으면 l1, 둘 중 하나만 값 있으면 값이 있는것 return
    
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not 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.mergeTowList(l1, l2)

✔ 풀이2 (퀵 정렬)

퀵 정렬 알고리즘으로 구현하면 타임아웃 발생.
-> 퀵 정렬을 변형해 좀 더 최적화를 진행해야함

퀵 정렬은 대표적인 불안정 정렬로, 같은 값이 반복될 경우에도 계속하여 스왑을 시도한다. 정렬된 리스트가 입력값으로 들어오게 된다면 계속해서 불균형 리스트로 나뉘게 되기 때문에 최악의 결과를 보인다.

✔ 풀이3 (내장 함수를 이용하는 실용적인 방법)

# 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]:
        #step1) 연결리스트를 파이썬의 리스트로 변경
        lst, p = [], head #리스트, 포인터 변수
        while p:
            lst.append(p.val)
            p = p.next
        
        #step2) 파이썬 sort() 메서드 사용하여 리스트 정렬
        lst.sort()
        
        #step3) 파이썬 리스트를 연결리스트로 변경
        p = head #포인터 변수
        for i in range(len(lst)):
            p.val = lst[i]
            p = p.next
        return head

📌 59) 구간 병합 ( 리트코드 56. Merge Intervals )

✔ 풀이 (정렬하여 병합)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort() #시작점 순으로 정렬
        
        merged = []
        for part in intervals:
            if merged and part[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], part[1])
            else:
                merged += [part]
                
        return merged

📌 60) 삽입 정렬 리스트 ( 리트코드 147. Insertion Sort List)

✔ 풀이1 (삽입 정렬)

# 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은 정렬이 된 리스트 / head는 정렬이 되지 않은 리스트를 가리킴
        cur = root = ListNode(None)
        while head:
            
            while cur.next and cur.next.val < head.val:
                cur = cur.next #cur이 head.val보다 이상인 값을 갖을 때 까지 이동
            
            cur.next, head.next, head  = head, cur.next, head.next
            
            cur = root #cur위치 초기화
        
        return root.next

📝 거의 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 insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = root = ListNode(0)
        while head:
            while cur.next and cur.next.val < head.val:
                #head가 들어갈 위치를 찾을때까지 cur이동
                cur = cur.next 
            
            cur.next, head.next, head= head, cur.next, head.next
            
            #조건을 걸어 cur의 위치를 초기화 (최적화)
            if head and cur.next.val > head.val:
                #cur위치 초기화
                cur = root
        
        return root.next

📌 61) 가장 큰 수 ( 리트코드 179. Largest Number )

✔ 풀이 (삽입 정렬)

class Solution:
    #swap여부 판단 함수
    @staticmethod
    def to_swap(n1, n2):
        return str(n1) + str(n2) < str(n2) + str(n1)
    
    def largestNumber(self, nums: List[int]) -> str:
        
        #삽입 정렬
        i = 1
        while i < len(nums):
            j = i
            while j > 0 and self.to_swap(nums[j - 1], nums[j]):
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
                j -= 1
            i += 1
            
        #'00'인 경우 '0'으로 출력해야함(예외경우)
        #->int형으로 형변환 후 다시 str형으로 형변환
        return str(int(''.join(map(str, nums)))) 
     

📌 62) 유효한 애너그램 ( 리트코드 242. Valid Anagram )

✔ 풀이 (정렬을 이용한 비교)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

📌 63) 색 정렬 ( 리트코드 75. Sort Colors )

✔ 풀이 (네덜란드 국기 문제를 응용한 풀이)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        #[정렬됨|정렬안됨|정렬됨]
        #       red   blue
        #red는 0이 들어갈 위치 (정렬이 안된 맨 왼쪽 부분)
        #white는 이동할 데이터의 위치, 
        #blue는 2가 들어갈 위치의 다음 위치를 가르킴 (정렬이 완료 된 오른쪽 파트의 맨 왼쪽 부분)
    
        red, white, blue = 0, 0, len(nums)
        while white < blue:
            if nums[white] < 1:
                nums[white], nums[red] = nums[red], nums[white]
                white += 1
                red += 1
            elif nums[white] > 1:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            else:
                white += 1
                
        return nums

📌 64) 원점에 k번째로 가까운 점 ( 리트코드 973. K Closest Points to Origin )

✔ 풀이 (유클리드 거리의 우선순위 큐 순서)

import heapq
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        #(거리, 좌표)로 최소힙에 추가
        Q = []
        for x, y in points:
            heapq.heappush(Q, (x ** 2 + y ** 2, [x, y]))
        
        #거리가 가까운 순으로 k개를 pop()하여 result에 좌표만 추가
        result = []
        for _ in range(k):
            point = heapq.heappop(Q)
            result.append(point[1])
        
        return result