leetcode 1405(그리디+heap), 143(linked list), 370(prefix sum), 739(stack, heap)

1405 https://leetcode.com/problems/longest-happy-string/
단순히 dfs로 짜면 시간초과가 나왔다. 더 효율적으로 생각해보다가 가장 긴 길이를 만들어내려면 현재 존재하는 a,b,c중에서 가장 많이 존재하는 단어를 먼저 사용하는 전략으로 결과값을 만들어야 한다. 단어와 단어 카운트를 기반으로 힙을 만들어준 후 남아있는 단어중 갯수가 가장 많이 남아있는것부터 빼서 계산하는식으로 처리한다.

from heapq import *

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        s = ''
        while a > 0 or b > 0 or c > 0:
            heap = []
            if a > 0 and s[-2:] != 'aa':
                heappush(heap, [-a, 'a'])
            if b > 0 and s[-2:] != 'bb':
                heappush(heap, [-b, 'b'])
            if c > 0 and s[-2:] != 'cc':
                heappush(heap, [-c, 'c'])
            if not heap:
                break
            count, word = heap[0]
            s += word
            if word == 'a':
                a -= 1
            elif word == 'b':
                b -= 1
            elif word == 'c':
                c -= 1
        return s

143 https://leetcode.com/problems/reorder-list/
root이후의 모든 노드를 덱에 넣어준 후에 한번은 오른쪽에서 빼고, 한번은 왼쪽에서 빼면서 끝까지 이어주면 된다.

from collections import deque

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        queue = deque()
        root = head
        while head:
            head = head.next
            if head:
                queue.append(head)
                
        node = root
        f = 1
        while True:
            if not queue:
                node.next = None
                break
            if f > 0:
                node.next = queue.pop()
            else:
                node.next = queue.popleft()
            f *= -1
            node = node.next

370 https://leetcode.com/problems/range-addition/
prefix sum과 관련된 문제다. 투 포인터나 그리디같은거인가? 하고 생각을 해봤는데 아이디어를 떠올리지 못해서 해답을 보고 정리해놓는다. https://leetcode.com/problems/range-addition/discuss/1339761/Detailed-explanation-or-Python여기에 너무너무너무 잘 설명되어있다.

1. start인덱스의 값을 inc만큼 증가시킨다.
2. end+1인덱스의 값을 inc만큼 감소시킨다.
모든 updates에 대해서 1,2번을 반복한 후 i+1에 i번째 값을 더해주면 prefix sum 이 쌓인다. 이런방법이 있구나..

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        ret = [0]*(length+1)
        for start, end, inc in updates:
            ret[start] += inc
            ret[end+1] -= inc
        for i in range(1, len(ret)):
            ret[i] += ret[i-1]
        return ret[:-1]

739 https://leetcode.com/problems/daily-temperatures/
그냥 최소힙으로 풀었다.

from heapq import *

class Solution:
    def dailyTemperatures(self, t: List[int]) -> List[int]:    
        d = {}
        heap = []
        for i,tt in enumerate(t):  # 모든 온도를 순회하면서
            heappush(heap, [tt, i])  # 최소힙에 온도를 가중치로 저장함.
            while heap:
                if tt > heap[0][0]:  # 현재의 온도보다 이전에 낮은 온도가 있었으면
                    d[heappop(heap)[1]] = i  # 이전온도와 현 온도를 맵핑시켜줌
                    continue
                break
        ret = []
        for i in range(len(t)):
            if i not in d:
                ret.append(0)  # 맵핑된게 없으면 0
            else:
                ret.append(d[i]-i)
        return ret

근데 monotone stack이라는 증가하는 값만 저장하는 스택으로 풀수도 있다. 
monotone stack : https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/
https://leetcode.com/problems/daily-temperatures/discuss/1575329/Python-monotonic-stack-explained
내가푼것과 방법론은 동일하다.