[Mock] Random 22

두번째 문제는.. 딴 문제로 착각해서 의도치 않은 3 문제 풀기...^^

---

1710. Maximum Units on a Truck

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

My Answer 1: Accepted (Runtime: 256 ms - 17.03% / Memory Usage: 14.7 MB - 70.80%)

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        ans = 0
        
        boxTypes = sorted(boxTypes, key=lambda unit: unit[1], reverse=True)
        
        for i in range(len(boxTypes)):
            if truckSize < boxTypes[i][0]:
                ans += truckSize * boxTypes[i][1]
                break
            else:
                ans += boxTypes[i][0] * boxTypes[i][1]
            truckSize -= boxTypes[i][0]
    
        return ans

Maximum Units 를 위해서 units 개수를 기준으로 오름차순 정렬한 후

sorted(boxTypes, key=lambda unit: unit[1], reverse=True) 정렬 방법 알아두기

boxTypes.sort(key=lambda x: -x[1]) => reverse 대신 음수 값 사용도 가능

큰 값부터 truckSize 에서 개수를 빼가면서 개수 * units 를 더해줌

if truckSize < boxTypes[i][0]: => 일부 박스만 사용해야하므로 개수 = truckSize

---

1721. Swapping Nodes in a Linked List

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

My Answer 1: Accepted (Runtime: 1168 ms - 25.72% / Memory Usage: 48.9 MB - 28.71%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        h1 = head
        cnt = 0
        n = 0
        arr = []
        
        while head:
            n += 1
            arr.append(head.val)
            head = head.next
            
        head = h1
        
        while head:
            cnt += 1
            
            if cnt == k:
                head.val = arr[-k]
            
            elif cnt == n - k + 1:
                head.val = arr[k-1]
                
            head = head.next
        
        return h1

swap 을 하려면 우선 두 값을 미리 알아야된다고 생각해서 리스트에 값들을 모두 담아줌 + 길이 구하기

다시 head 부터 돌려서 앞에서 k 번째와 뒤에서 k 번째값을 swap

Solution 1: Accepted (Runtime: 1144 ms - 30.07% / Memory Usage: 48.7 MB - 94.45%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        first = last = head
        for i in range(1, k):
            first = first.next

        null_checker = first 
        while null_checker.next:
            last = last.next
            null_checker = null_checker.next
        first.val, last.val = last.val, first.val
        return head

first 는 앞에서 k 번째 값을 가리키도록 하고 last 는 뒤에서 k 번째 값을 가리키도록 함

그 다음 val 값만 swap

Solution 2: Accepted (Runtime: 1352 ms - 14.14% / Memory Usage: 48.9 MB = 56.44%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        dummy = pre_right = pre_left = ListNode(next=head)
        right = left = head
        for i in range(k-1):
            pre_left = left
            left = left.next

        null_checker = left

        while null_checker.next:
            pre_right = right
            right = right.next
            null_checker = null_checker.next

        if left == right:
            return head

        pre_left.next, pre_right.next = right, left
        left.next, right.next = right.next, left.next
        return dummy.next

아예 node 를 swap 하는 방식

pre_left, pre_right, left, right 네가지 포인터를 이용해서

pre_left, left 는 앞에서 k-1, k 번째 값을 가리키도록 하고
pre_right, right 는 뒤에서 k+1, k 번째 값을 가리키도록 함

pre 들을 이용해서 node swap

---

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

My Answer 1: Accepted (Runtime: 64 ms - 5.47% / Memory Usage: 14.3 MB - 14.59%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pair = 0
        h1 = ListNode(0, head)
        h2 = h1
        
        while h1:
            if h1.next and h1.next.next:
                tmp1 = ListNode(h1.next.val, h1.next.next.next)
                tmp2 = ListNode(h1.next.next.val, tmp1)
                h1.next = tmp2
                h1 = h1.next.next
            else:
                h1 = h1.next
        
        return h2.next

맨 앞에 dummy node 를 추가해서 next 와 next.next 두개를 묶음으로 확인함

tmp1 에는 뒤로 갈 값을, tmp2 에는 앞으로 올 값을 넣어서 next = tmp2

swap 하면 두칸씩 이동하기

문제가 비슷해서... 이 문제인줄 알고 풀다가 중간에 아닌 걸 깨달음..ㅎ

Solution 1: Accepted (Runtime: 76 ms - 5.47% / Memory Usage: 14.4 MB - 14.59%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        return self.next

비슷한데 아예 while 문의 조건으로 pre.next and pre.next.next 를 주기

swap 할 때는 새 노드 생성 없이 pre.next, b.next, a.next = b, a, b.next