Leetcode Java IPO

문제

Link

코드

class Solution {

  public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    Queue<int[]> profitsQueue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    Queue<int[]> capitalQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    for (int idx = 0; idx < profits.length; idx++) {
      if (capital[idx] <= w) {
        profitsQueue.add(new int[] { profits[idx], idx });
      } else {
        capitalQueue.add(new int[] { capital[idx], idx });
      }
    }
    while (k-- > 0 && !profitsQueue.isEmpty()) {
      w += profitsQueue.poll()[0];
      while (!capitalQueue.isEmpty() && capitalQueue.peek()[0] <= w) {
        profitsQueue.add(new int[] { profits[capitalQueue.poll()[1]], 0 });
      }
    }
    return w;
  }

}

결과

Link

설명

1. w의 초기 자본으로 k개의 개별 프로젝트의 순수 이익인 profits과 최소 자본인 capital을 이용하여 각 최대화된 최종 자본을 반환하는 문제이다.

2. 이익과 자본을 정렬화된 Queue에 넣어 사용하기 위한 profitsQueue와 capitalQueue를 정의한다.
   • profitsQueue는 내림차순, capitalQueue는 오름차순으로 정렬한다.
3. 0부터 profits의 길이 미만까지 idx를 증가시키며 아래를 반복한다.
   • capital의 idx번째 값이 w 이하인 경우, profitsQueue에 profits의 idx번째 값과 idx를 배열로 넣어준다.
   • capital의 idx번째 값이 w 초과인 경우, capitalQueue에 capital의 idx번째 값과 idx를 배열로 넣어준다.
4. k가 0 초과이고, profitsQueue가 비어있지 않을 때 까지 아래를 반복하고 매 횟수마다 k를 감소시킨다.

• w에 profitsQueue의 배열을 꺼내 첫 값인 이익을 더해준다.
• capitalQueue가 비어있지 않고, capitalQueue의 다음 배열의 첫 번째 값이 w 이하일 때 까지 반복하여 아래를 수행한다.
  • profitsQueue에 capitalQueue에서 꺼낸 배열의 두 번째 값인 위치 값에 해당하는 profits의 값을 꺼내 새 정수 배열로 0과 함께 넣어준다.

1. 반복이 완료되면 최대화된 자본을 저장한 w를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.