[leetcode] 그리디 알고리즘 모음집.zip

그리기 알고리즘의 핵심은

그때그때 가장 적합한 선택을 하는 것!

 

122번. 주식 팔고사기 

가장 적합한 선택 -> 바로 다음 값이 오르면 팔고, 아니면 만다!

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0 # 결과 저장
        for i in range(len(prices)-1):
            if prices[i+1]>prices[i]: # 다음 값이 크면 판다!
                result += prices[i+1]-prices[i]
        return result

 

406번. 키에 따라 재정렬

가장 적합한 선택 -> 키(역순)/인덱스 순으로 정렬한 뒤 인덱스대로 삽입

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(-x[0], x[1]))
        
        answer=[]
        while people:
            person = people.pop(0)
            answer.insert(person[1], person)
        
        return answer

 

134번. Gas Station

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:  
        for start in range(len(gas)):
            fuel = 0 
            for i in range(start, len(gas)+start):
                idx = i%len(gas)
                
                travel = True
                if gas[idx] + fuel < cost[idx]:
                    travel = False
                    break
                else:
                    fuel += gas[idx]-cost[idx]
            if travel:
                return start 
        return fuel

 

621번. 태스크 스케줄러

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        
        counter = collections.Counter(tasks)
        result = 0
        
        while True:
            sub_count = 0

            # 그때그때의 최빈값을 n+1개만큼 출력
            for task, _ in counter.most_common(n+1):
                result += 1
                sub_count += 1
                counter.subtract(task)

                # 0 이하인 아이템을 목ㅁ록에서 완전히 제거
                counter += collections.Counter()


            if not counter:
                break
            
            # n(간격)-sub_count(간격) = 0이 나와야함, +1은 idl이라고 대충 생각
            result += n-sub_count+1
        return result

 

455. 쿠키 나눠주기

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        print(g, s)
        
        count = 0
        while g:
            kid = g.pop(0)
            
            for cookie in s:
                if cookie >= kid:
                    s.remove(cookie)
                    count += 1
                    break
            
        return count