[leetcode] 146, 148, 268, 283

268. Missing Number

https://leetcode.com/problems/missing-number/

My Answer 1: Accepted (Runtime: 132 ms - 61.74% / Memory Usage: 15.4 MB - 79.40%)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        start = 0
        if nums[0] != 0:
            return 0
        
        for i in range(1, len(nums)):
            if start+1 != nums[i]:
                return start+1
            start += 1
        
        return nums[-1] + 1

정렬해서 0 ~ n 까지 연속인지 확인

연속하지 않으면 끊긴 값 return

끝까지 봤으면 마지막 값 + 1 return

이 외에도 in 을 사용하는 방식도 해봤지만

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

이걸 만족하지 못함...

Solution 1: Accepted (Runtime: 124 ms - 89.20% / Memory Usage: 15.5 MB - 49.03%)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n*(n+1)//2
        return expected_sum - sum(nums)

Gauss' Formula
=> 0 ~ n 의 전체 합 - 주어진 nums 의 합

---

283. Move Zeroes

https://leetcode.com/problems/move-zeroes/

My Answer 1: Accepted (Runtime: 124 ms - 15.39% / Memory Usage: 15.4 MB - 65.36%)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = 0
        while 0 in nums:
            count += 1
            nums.remove(0)
        
        for i in range(count):
            nums.append(0)

0 들을 모두 제거해주고

그 개수만큼 다시 뒤에 append

Solution 1: Accepted (Runtime: 48 ms - 77.21% / Memory Usage: 15.4 MB - 65.36%)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        for j in range(len(nums)):
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

인덱스 i 에 0 이 아닌 숫자들을 고정시킴

---

146. LRU Cache

https://leetcode.com/problems/lru-cache/

My Answer 1: Accepted (Runtime: 2680 ms - 7.87% / Memory Usage: 74 MB - 75.12%)

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.recent = []

    def get(self, key: int) -> int:
        if key in self.cache:
            if self.recent[-1] != key:
                self.recent.remove(key)
                self.recent.append(key)
            return self.cache[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            if self.recent[-1] != key:
                self.recent.remove(key)
                self.recent.append(key)
        else:
            if len(self.cache) == self.capacity:
                k = self.recent.pop(0)
                del self.cache[k]
            self.cache[key] = value
            self.recent.append(key)


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

cache: dictionary 에 key-value 형식으로 저장
capacity: 최대 size
recent: 최근 사용한 순서대로 key 값들 저장 (마지막 값이 가장 최근에 사용)

get)
key 값이 cache 에 존재하면 recent 순서 업데이트 후 return

put)
key 값이 cache 에 존재하면 value update & recent 순서 업데이트 후 return

존재하지 않을 경우 (새로 넣어야 할 경우) 는
사이즈가 꽉 찼으면 recent.pop(0) key 를 cache 에서도 삭제 처리
cache & recent 모두 새로 넣어주기

루션이 중에 linked list 를 사용하는게 있긴 하지만...
지금 풀이가 더 이해하기 좋다고 생각..^^

---

148. Sort List

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

My Answer 1: Time Limit Exceeded (24 / 28 test cases passed.)

# 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]:
        if head is None:
            return None
        
        h = head
        length = 0
        while head:
            length += 1
            head = head.next
        
        prev = h
        head = h.next
        for i in range(length):
            p = prev
            while head:
                if prev.val > head.val:
                    prev.val, head.val = head.val, prev.val
                prev = prev.next
                head = head.next
            prev = p
            head = p.next
        
        return h

우선 전체 길이 계산 => length

prev 는 head 의 이전 노드를 가리키도록 함

length 길이 만큼 for 문 돌리면서 버블정렬 하듯이
현재 head 값이 위치할 곳을 찾아 계속 swap

prev, head 는 다음 값으로 이동

Solution 1: Accepted (Runtime: 468 ms - 63.01% / Memory Usage: 30.2 MB - 35.27%)

# 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: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        p, slow, fast = None, head, head
        while fast and fast.next:
            p = slow
            slow = slow.next
            fast = fast.next.next
        p.next = None
        
        return self.merge(self.sortList(head), self.sortList(slow))
    
    def merge(self, l1, l2):
        dummy = ListNode(None)
        curr = dummy
        
        while l1 and l2:
            if l1.val > l2.val:
                curr.next, l2 = l2, l2.next
            else:
                curr.next, l1 = l1, l1.next
            curr = curr.next
        
        if l1:
            curr.next = l1
        elif l2:
            curr.next = l2
        
        return dummy.next

slow, fast 로 slow 를 중간 노드에 위치하도록 해서
절반으로 나눔 => p.next = None

각 반씩 merge 하기 => merge(self.sortList(head), self.sortList(slow))

merge)
dummy 노드를 만들고
l1, l2 두 노드 값을 동시에 비교하면서 더 작은 값을 curr 에 붙여줌

남은 노드는 뒤에 붙여주기

냅다 외워!!!