99클럽 코테 스터디 23일차 TIL, leetcode / IPO

🔑 오늘의 학습 키워드 heap

🔗 문제링크 https://leetcode.com/problems/ipo/

 

# 현재 가지고 있는 상품 중에서 가장 좋은 것을 선택
# 자료구조 heap을 사용해서 pop할 때마다 비교하면서 가장 좋은 것을 선택
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        projects = sorted(list(zip(capital, profits)))       
        max_heap = []
        i = 0
        for _ in range(k):
            # 현재 자본(w)으로 할 수 있는 모든 프로젝트
            while i < len(projects) and projects[i][0] <= w:
                heapq.heappush(max_heap, -projects[i][1])
                i += 1
            
            # 할 수 있는 프로젝트가 없으면 종료
            if not max_heap:
                break
            
            # 가장 이익이 높은 프로젝트를 수행
            w -= heapq.heappop(max_heap)
        
        return w

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

냅색 알고리즘인가? 싶었지만 현재 가지고 있는 자본에 의해 다음이 결정됐기 때문에 그리디로 풀어야한다고 생각을 했다

 

그리고 가격이랑 이익이 따로따로 되어 있어서 zip을 사용해서 묶은 다음 정렬해서 풀면 좋을 것 같다고 생각을 했고

 

k번 반복하면서 현재 할 수 있는 애들 중 가장 이익이 높은 애들을 더해주면 된다고 생각했다.

 

또한 최대 값을 계속 구해야 하는 구조이기 때문에 heap을 사용하면 좋을 것 같다고 생각했다.

⏰ 예상 시간 복잡도 O(NLogN+KLogN)

제한 사항

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

😎 알고리즘 개요

1. 프로젝트를 zip 함수로 묶은 후 정렬을 해줬다. 

2. 낮은 가격부터 쭉 heap에 담아가며 현재 자본을 넘지 않는 선에서 최대의 이익을 가진 프로젝트를 선택

✅ 오늘의 회고

- 적절한 자료구조를 사용하는 것이 중요하다

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL