Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] IPO

[IPO]

• 그리디하게 보유한 capital 내에서 가장 큰 profit을 얻을 수 있는 project를 $k$번 선택하면 된다.

Solution 1. Sort + Binary Search $O(n \lg n+ k(n^2 +n \lg n))$

def bs_ub(self, a, v):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid] <= v:
            lo = mid+1
        else:
            hi = mid-1
    
    return lo

def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
    proj = sorted(zip(capital, profits))
    i = 0

    possible = []
    for _ in range(k):
        while i < len(proj) and proj[i][0] <= w:
            possible.insert(self.bs_ub(possible, proj[i][1]), proj[i][1])
            i += 1

        if possible: w += possible.pop()
        else: break
    
    return w

• capital로 w과 비교하고, 그 인덱스에 대응하는 profits 의 값을 이용해야 하므로 같이 관리하기 좋게 zip()으로 묶어준다.
• 필요 capital이 낮은 proj부터 순회하며 가능한 프로젝트의 목록(possible)을 갱신해준다.
• 이 때, $O(1)$에 가장 큰 이득을 얻을 수 있는 프로젝트를 진행할 수 있도록 가능한 후보들을 일단 추가한 다음에($O(m)$) 리스트를 매번 정렬하면 TLE가 난다.
  • 이를 편법으로(시간복잡도를 약간 낮춘 방식으로) 해결할 수 있다(물론 이 편법 또한 테스트케이스가 약해서 가능하다).
  • 매번 정렬을 수행할 게 아니라, 정렬된 상태를 유지시킬 수 있도록 삽입하는 방법이다.
    • possible 리스트는 정렬된 상태임을 생각하면, 이분 탐색을 이용하여 삽입될 원소가 들어갈 자리를 $O(\lg m)$에 구할 수 있고, 그 자리에 삽입한다.
      • 이 때, 같은 값을 가지는 profits에 대하여 최대한 리스트의 오른쪽에 삽입하는 것이 삽입에 더 짧은 시간이 소요되므로 Upper bound를 이용한다.
    • 리스트에 원소를 삽입하는 연산은 최악의 경우 $O(m)$이다. 이는 리스트의 첫 번째 자리에 원소가 추가되면 다른 모든 원소의 인덱스를 조정해주어야 하기 때문이다.
    • 하지만 capital의 값이 증가함에 따라 profits의 값도 증가하는 경향을 가진 테스트 케이스들(possible의 상대적으로 뒷부분에 insert하는 경우)로 구성된 것인지, 삽입에 많은 시간이 걸리지 않아 통과된다.

Solution 2. Sort + Heap $O(n \lg n + k \cdot n \lg n)$

def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
    proj = sorted(zip(capital, profits), key=lambda x: x[0])

    i = 0
    possible = []
    for _ in range(k):
        while i < len(proj) and proj[i][0] <= w:
            heappush(possible, -proj[i][1])
            i += 1
        
        if possible: w -= heappop(possible)
        else: break
    
    return w

• 최댓값을 지속적으로 갱신해야 하고, 지속적으로 최댓값을 이용한다는 점을 생각하면 heap을 이용하는 것이 가장 깔끔하고 빠르다.
• 정렬에서 실행 시간을 조금이라도 쥐어짜볼만한 포인트가 있는데, 어차피 profits는 heap에 push될 때 정렬 과정을 수행한 뒤 push된다는 점을 생각하면, 미리 정렬해놓을 필요가 없다. 따라서, 정렬 시 capital만을 기준으로 정렬하도록 key=lambda x: x[0]으로 지정하면, 같은 capital 값을 가질 때 profits 는 비교하지 않기 때문에 조금이라도 빨라질 여지가 있다.

  • 이를 다르게 생각하면 zip() 으로 묶지 않고 enumerate() 로 인덱스만 갖고 있는 방법도 생각해볼 수 있다. 아래 두 줄만 변경해주면 된다.

    proj = sorted(enumerate(capital), key=lambda x: x[1])
    heappush(possible, -profits[proj[i][0]])

Solution 3. Heap $O(n + k \cdot n \lg n)$

def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
    proj = [*zip(capital, profits)]
    heapify(proj)
    
    possible = []
    for _ in range(k):
        while proj and proj[0][0] <= w:
            heappush(possible, -heappop(proj)[1])
        
        if possible: w -= heappop(possible)
        else: break
    
    return w

• capital의 최솟값을 기준으로 계속해서 갱신한다는 점을 생각하면, 이 또한 $O(n \lg n)$이 걸리는 정렬이 아닌 $O(n)$이 걸리는 heapify()를 이용할 수 있다.
• 이를 통해 정렬에 걸리는 시간인 $O(n \lg n)$을 반정렬 상태인 heap을 이용하여 $O(n)$으로 바꿀 수 있으나,
  • possible을 갱신할 때마다 $O(\lg n)$의 시간이 추가로 소모되어 이 또한 최악의 경우($k\ge n)$ 기존 방식과 같은 시간이 걸리며,
  • Tim sort는 최선의 경우 $O(n)$의 시간이 소요된다는 점을 감안하면 오히려 이 방법이 느릴 수 있다.

---