# 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)
퀵 정렬 알고리즘으로 구현하면 타임아웃 발생.
-> 퀵 정렬을 변형해 좀 더 최적화를 진행해야함
퀵 정렬은 대표적인 불안정 정렬로, 같은 값이 반복될 경우에도 계속하여 스왑을 시도한다. 정렬된 리스트가 입력값으로 들어오게 된다면 계속해서 불균형 리스트로 나뉘게 되기 때문에 최악의 결과를 보인다.
# 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
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
# 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초가 걸림. 조금 더 최척화할 방법 찾아야함!
# 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
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))))
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
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
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