[Algorism/HackerRank] Luck Balance

👉 문제 링크

✏️ 문제 요약

• 주인공은 행운이 축적된다고 믿으며, 코딩 대회를 준비중
  코딩 대회에서 이기면 행운이 감소하고, 진다면 행운이 추가된다고 믿음

• 대회별로 행운 수치가 다름

• 가장 큰 행운 축적값을 구하고자 함

• 단, 중요한 대회는 k번이 있으며 k번은 무조건 져야함
  그리고 k번을 지고난 이후의 중요한 대회는 무조건 이겨야함

💡 문제 풀이

• 대회를 이기든, 지든 문제 풀이와는 연관 없음

• 모든 대회를 지는 것이 가장 큰 행운 축적값이 됨

• 탐욕 알고리즘을 사용해 보면 직관적으로 행운 수치가 큰 대회를 지면 됨
  중요한 대회에서는 점수가 큰 k번의 대회에서 지고, 이외에 중요한 대회에서는 이기면 됨
  계산을 쉽게 하기 위해 정렬을 이용

💻 구현 코드

1. 주어진 배열을 우선 정렬
   중요도가 높은 순서로 먼저 정렬
   중요도가 동일한 경우는 행운 수치가 높은 순서로 정렬(중요하지 않은 대회는 정렬이 필요없긴 함)

2. 중요한 대회는 k번을 지고, 나머지는 이김
   중요하지 않은 대회는 모두 짐

코드 보기

  public static int luckBalance(int k, int[][] contests) {
      sortOrderByImportantAndLuckValue(contests);

      int balance = 0;

      for (int i = 0; i < contests.length; i++) {
          if (contests[i][1] == 1) {
              if (k > 0) {
                  k--;        // 중요한 경기는 k번만 가능함
                  balance += contests[i][0];      // 이미 행운 값이 큰 순서로 정렬이 되어 있으므로 k번의 중요 경기는 모두 지는 것으로 간주
              } else {
                  balance -= contests[i][0];
              }
          } else {
              balance += contests[i][0];
          }
      }

      return balance;
  }

  /**
   * 중요도 높은 순서(중요 -> 비중요)로 우선 정렬(내림차순)
   * 중요도가 동일한 경우, 행운 값이 더 많은 순서로 정렬(내림차순)
   */
  public static void sortOrderByImportantAndLuckValue(int[][] arr) {
      Arrays.sort(arr, (a, b) -> {
          if (a[1] < b[1]) {
              return 1;
          } else if (a[1] == b[1]) {
              return b[0] - a[0];
          } else {
              return -1;
          }
      });
  }