[5부 알고리즘] 21장 그리디 알고리즘

📌 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