algorithm/problem solving
leetcode 1405(그리디+heap), 143(linked list), 370(prefix sum), 739(stack, heap)
qkqhxla1
2021. 12. 25. 15:31
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