[TIL_Carrotww] 90 - 23/01/23

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 316 Remove Duplicate Letters Medium

문제를 이해하는데 조금 걸렸지만 엄~~청 어려운 문제는 아니고 살짝 까다로운 문제이다.

• 풀이

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        import collections
        counter = collections.Counter(s)
        stack = []

        for char in s:
            counter[char] -= 1
            if char in stack:
                continue

            while stack and char < stack[-1] and counter[stack[-1]] >= 1:
                stack.pop()

            stack.append(char)

        return ''.join(stack)

Counter()를 사용하여 글자가 몇번씩 쓰였는지 체크한다.
while문 부분은 먼저 나온 (stack에 먼저 들어가있는 문자 stack[-1]) 문자가 현재 문자(char) 보다 사전적으로 뒤에 있고,
반복문 뒤에 더 남아있다면 (counter[stack[-1]]) stack에서 계속 제거해준다.

위 설명의 while문 부분만 이해한다면 크게 문제될건 없는 문제이다.

🔍 Leetcode 739 Daily Temperatures Medium

이제 스택 문제는 쉬운것 같다.

• 풀이

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = [0 for _ in range(temperatures)]
        stack = []

        for i in range(temperatures):
            while stack and temperatures[stack[-1]] < temperatures[i]:
                index = stack.pop()
                result[index] = i - index
            stack.append(i)

        return result

혹시 몰라서 bruteforce로 해보았는데 역시나 시간초과 난다.

🔍 Leetcode 23 Merge k Sorted Lists Hard

heapq를 사용하는 문제이며 listnode가 포함되어 있다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import List, Optional
import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        root = result = ListNode(None)
        heap = []

        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))

        while heap:
            node = heapq.heappop(heap)
            index = node[1]
            result.next = node[2]

            result = result.next
            if result.next:
                heapq.heappush(heap, (result.next.val, index, result.next))

        return root.next

🧲 python의 PriorityQueue VS heapq

🔍 java에 priorityQueue가 있다.
기본적으로 priorityQueue와 heapq의 기능은 같으며 priorityQueue 내부 put, get 메서드는 heapq 모듈을 사용하여 동작하여 동일하다고 볼 수 있다.

하지만 heapq는 스레드 세이프를 보장하지 않는다.
그렇지만 python에서는 heapq를 많이 사용한다. 이유는 python은 GIL 특성으로 멀티 스레딩이 거의 의미가 없기 때문이다.
PriorityQueue 모듈의 스레딩 지원은 큰 의미가 없으며, 멀티 스레딩을 지원하여 내부적으로 락킹을 제공해 락킹 오버헤드가 발생해 성능에 영향을 끼치기 때문이다.