[python3] 502. IPO

풀이 일자: 23.02.23

난이도: [Hard]

분류: [Heap, Sorting, Greedy]

문제 내용

k = 최대로 진행할 수 있는 프로젝트 개수( 서로 다른 프로젝트)

w = 현재 가지고 있는 자본

profits[i] = i번째 프로젝트를 해서 얻게 되는 순이익

capital[i] = i번째 프로젝트를 하기 위한 최소 자본

 

최대 k개의 프로젝트를 진행하여 w를 최대로 만드는 문제였다.

 

 

문제 해결 흐름(내 풀이)

1.우선 k개의 프로젝트를 진행하여 w를 최대로 만드는 것이기에 뭔가 Greedy하게 처리할 수 있지 않을까라는 생각..

→ w의 자본이 있다고 했을 때 capital중에 w이하인 인덱스를 찾아서 profits 배열을 탐색 후 제일 큰 값 찾기

 

## 배열이 작은 경우에는 잘 처리가 되었으나 큰 경우에는 TLE가 나왔다.
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:

        pc = list();
        for i in range(len(profits)):
            pc.append([capital[i], profits[i], 0])
            
        pc = sorted(pc, key = lambda x: (x[0], -x[1]));

        while(k > 0):
            maxi = -1; maxV = 0; prevV = -1;
            for i in range(len(pc)):
                if w >= pc[i][0]:
                    if pc[i][2] == 0 and maxV < pc[i][1] and prevV != pc[i][0]:
                        maxi = i; maxV = pc[i][1];
                        prevV = pc[i][0];
                else:
                    break;
            
            if maxi == -1:
                break;

            w += maxV;
            k -= 1;
            pc[maxi][2]= 1;

        return w;

=> 일단은 기본적인 TC를 모두 통과하였으나 k와  주어진 프로젝트의 크기가 큰 경우 처리하는 시간이 많이 걸려 결국 TLE가 나왔다.

 

 

2. 현재 위의 코드에서 TLE가 나오는 까닭은 배열의 탐색을 계속적으로 하기 때문에 발생하는 것으로 이에 적합한 자료구조가 필요한 것 같다.

→ 항상 profit이 가장 큰 것을 찾아야 하고 탐색시간이 짧아야 하니까 이 조건에 맞는 자료구조는 Heap이다.

#큰 경우에 대해 Wrong Answer가 뜸..
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:

        pc = [];
        for i in range(len(profits)):
            pc.append([capital[i], profits[i]])

        pc = sorted(pc, key=lambda x: x[0]);

        capital = [];
        profits = [];
        
        for i in range(len(pc)):
            if pc[i][0] not in capital:
                capital.append(pc[i][0]);
                profits.append([-pc[i][1]]);
            else:
                idx = capital.index(pc[i][0]);
                heapq.heappush(profits[idx], -pc[i][1]);
        
        while(k > 0):
            maxV = 0; maxi = -1;
            for i in range(len(capital)):
                if capital[i] <= w:
                    if len(profits[i]) != 0:
                        maxV = max(maxV, -profits[i][0]);
                        maxi = i;
                else:
                    break;

            if maxi == -1:
                break;
            else:
                w += maxV;
                k -= 1;
                heapq.heappop(profits[maxi]);

        return w;

=> Heap을 사용했는데 오히려 많은 프로젝트에 대한 TC에 대해서 Wrong Answer가 나오게 된다.

 

다른 해결 방식( Offical Solution or User's)

1. 결국에는 Official Solution을 확인했는데 내가 너무 어렵게 생각했던 것으로 보인다.

→ (capital, profit)의 쌍을 가지고 heap을 만들어버리면 찾기 어려울 것이라 생각했는데 capital을 기준으로 sorting을 진행하고 w의 범위 내에서만 heap을 만들어서 최댓값을 뽑아내기만 한다면 되었다.

 

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:

        n = len(profits);
        pc = list(zip(capital, profits));
        pc.sort();                               # [capital, profits]쌍을 만들어 capital로 sort

        q = [];                                  # heap
        idx = 0;                                 # pc 탐색 인덱스

        for i in range(k):                       # 할 수 있는 최대 프로젝트 개수
            while idx < n and pc[idx][0] <= w:   # pc를 다 탐색하지 않았거나 초기 예산 조건에 부합하면
                heappush(q, -pc[idx][1]);        # 넣는데 -를 붙이는 이유는 heapq는 min heap으로 max heap으로 사용하기 위해서이다.
                idx += 1;
            
            if len(q) == 0:                      # heap에 없다는 것은 더이상 넣을 수 있는 프로젝트가 없다는 의미
                break;
            w += -heappop(q)                     # 현재 예산 내의 profits값 중 최대값을 heap으로 찾아 예산에 더함

        return w;

Time Complexity: O(NlogN)

시간복잡도는 sort()함수의 시간복잡도인 nlogn을 가질 것이다.

 

Space Complexity: O(N)

capital과 profits의 쌍의 갯수인 N만큼의 공간복잡도를 가질 것이다.

 

 

문제 링크

https://leetcode.com/problems/ipo/description/

IPO - LeetCode