📌 78) 주식을 사고 팔기 가장 좋은 시점 ( 리트코드 122. Best Time to Buy and Sell Stock II )
✔ 풀이1 (그리디 알고리즘)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(len(prices) - 1):
if prices[i] < prices[i + 1]: #다음날 주식이 오를 경우
profit += prices[i + 1] - prices[i]
return profit✔ 풀이2 (파이썬 다운 방식)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum([max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1)])📌 79) 키에 따른 대기열 재구성 ( 리트코드 406. Queue Reconstruction by Height )
✔ 풀이 (우선순위 큐 이용)
import heapq
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
hq = []
#키가 최대인 사람 먼저 추출할 수 있도록 최대 힙 구성
for person in people:
heapq.heappush(hq, (-person[0], person[1]))
#키가 최대인 사람 먼저 추출
answer = []
while hq:
person = heapq.heappop(hq)
#이미 자신보다 큰 사람들은 배치 완료 됨
#따라서 앞에 줄서 있는 사람 중 자신의 키 이상인 사람들의 수 = 추가 할 index
answer.insert(person[1], [-person[0], person[1]])
return answer📌 80) 태스크 스케줄러 ( 리트코드 621. Task Scheduler)
✔ 풀이1 (Counter사용)
from collections import Counter
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
counter = Counter(tasks)
result = 0
while 1:
pop_cnt = 0
for task, _ in counter.most_common(n + 1): #task실행
pop_cnt += 1
result += 1
#실행한 결과 counter에 반영
counter.subtract(task)
#값이 0이하이면 아이템 목록에서 제거
counter += Counter()
#while문 종료조건 = 모든 task를 실행 했을 경우
if not counter:
return result
#task를 n+1개 실행했으면 result는 그대로
result += n - pop_cnt + 1✔ 풀이2 (heapq, Counter사용)
from collections import Counter
import heapq
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
Q = []
for task, num in Counter(tasks).items():
Q.append((-num, task))
result, temp = 0, []
while 1:
pop_cnt = 0
heapq.heapify(Q)
for _ in range(n + 1):
if Q:
num, task = heapq.heappop(Q)
if num + 1:
temp.append((num + 1, task))
result += 1
pop_cnt += 1
Q, temp = temp + Q, [] #남아있는 작업을 Q에 다시 추가
if not Q: #while문 종료조건 = 모든 작업 수행했을 경우
return result
result += n - pop_cnt + 1👉 풀이1은 Counter모듈을 무리하게 사용한 탓에 속도가 느림.
👉 풀이2는 Counter모듈 연산을 빼고, heapq모듈로 로직 구성하여 풀이1보다 약 2배 빠른 속도를 갖음
📌 81) 주유소 ( 리트코드 134. Gas Station )
✔ 풀이1 (모두 방문)
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
for start in range(n):
i, cnt = start, n #시작위치, 최대 이동 횟수
fuel = gas[i] #현재 연료
while cnt:
next_i = (i + 1) % n #다음 위치
can_travel = True
if fuel < cost[i]: #연료가 모자를 경우
can_travel = False
break
fuel = fuel - cost[i] + gas[next_i]
i = next_i #이동 완료
cnt -= 1
if can_travel:
return start
return -1👉 두 번의 루프가 중첩되어 있으므로 O(n2)
👉 조금 더 최적화 필요
✔ 풀이2 (한번 방문)
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
#닶이 존재하지 않는 경우
if sum(gas) < sum(cost):
return -1
#여기서부턴 무조건 답이 1개 존재
#출발점이 안 되는 지점 판별
start, fuel = 0, 0
for i in range(len(gas)):
if fuel + gas[i] < cost[i]: #이동 할 연료 모자를 경우
#해당 지점이 출발점이 안 되는 지점으로 판별하면
#앞에 있는 모든 지점들도 출발점이 될 수 없음
start = i + 1 #start를 다음으로 이동
fuel = 0 #연료 초기화
else:
fuel += gas[i] - cost[i]
return start👉 O(n) 으로 최적화 완료
👉해당 지점이 출발점이 안 되는 지점으로 판별되면, 앞에 있는 모든 지점들도 출발점이 될 수 없음!
어떤 출발 지점에서 (지점 연료 - 이동하는데 필요한 연료)가 A, B, C, D... 라고 하자
각각 현재 (내가 가지고 있는 연료 - 이동하는데 필요한 연료) 가 0이상이어야 이동이 가능하다.
다음과 같은 상황을 가정하자.
1번째 A >= 0 이동 가능
2번째 A + B >= 0 이동 가능
3번째 A + B + C < 0 이동 불가능 => 즉, C < (-A) + (-B)
3번째에서는 이동할 수 없다. 그럼 2번째에서 출발하면 전체순회가 가능할까?
2번째에서 처음 출발 해보자
2번째 B >= 0 이동 가능 (가정)
3번째 B + C 는 어떻게 될까?
-> 위에서 C < (-A) + (-B)이므로 B + C < (-A) 이다.
B + C < (-A)에서 A >= 0이므로 B + C < 0 이다.
즉, B + C < 0 이므로 2번째에서 출발 하더라도 3번째에서 이동이 불가능 하므로 전체순회 가능하지 않다.
따라서, 해당 지점이 출발점이 안 되는 지점으로 판별되면, 앞에 있는 모든 지점들도 출발점이 될 수 없다
📌 82) 쿠키 부여 ( 리트코드 455. Assign Cookies )
✔ 내 풀이
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
answer, child_i, cookie_i = 0, 0, 0
while 1:
if child_i >= len(g) or cookie_i >= len(s):
return answer
if g[child_i] <= s[cookie_i]: #만족할 경우
child_i += 1
cookie_i += 1
answer += 1
else:
cookie_i += 1✔ 풀이1 (그리디 알고리즘)
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
child_i = cookie_i = 0
while child_i < len(g) and cookie_i < len(s):
if g[child_i] <= s[cookie_i]: #만족할 경우
child_i += 1
cookie_i += 1
return child_i✔ 풀이2 (이진 검색)
import bisect
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
#하나의 리스트를 순회하면서 다른 하나는 이진검색으로 찾음
child_i = 0
for i in s:
index = bisect.bisect_right(g, i) #g에 i값을 추가 가능한 가장 오른쪽 위치
if child_i < index:
child_i += 1
return child_i