Luck Balance

🔗 문제 링크

https://www.hackerrank.com/challenges/luck-balance/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=greedy-algorithms

❔ 문제 설명

Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. Initially, her luck balance is 0. She believes in "saving luck", and wants to check her theory. Each contest is described by two integers, L[i] and T[i]:

L[i] is the amount of luck associated with a contest. If Lena wins the contest, her luck balance will decrease by L[i]; if she loses it, her luck balance will increase by L[i].
T[i] denotes the contest's importance rating. It's equal to 1 if the contest is important, and it's equal to 0 if it's unimportant.
If Lena loses no more than k important contests, what is the maximum amount of luck she can have after competing in all the preliminary contests? This value may be negative.

Example

k = 2
L = [5,1,4]
T = [1,2,0]

Contest	     L[i]	T[i]
   1	       5	 1
   2	       1	 1
   3	       4	 0

If Lena loses all of the contests, her will be 5 + 1 + 4 = 10 . Since she is allowed to lose 2 important contests, and there are only 2 important contests, she can lose all three contests to maximize her luck at 10.

If k = 1, she has to win at least 1 of the 2 important contests. She would choose to win the lowest value important contest worth 1. Her final luck will be 5 + 4 - 1 = 8.

Function Description

Complete the luckBalance function in the editor below.

luckBalance has the following parameter(s):

• int k: the number of important contests Lena can lose
• int contests[n][2]: a 2D array of integers where each contests[i] contains two integers that represent the luck balance and importance of the $i^{th}$ contest

Returns

• int: the maximum luck balance achievable

Input Format

The first line contains two space-separated integers n and k, the number of preliminary contests and the maximum number of important contests Lena can lose.
Each of the next n lines contains two space-separated integers, L[i] and T[i], the contest's luck balance and its importance rating.

⚠️ 제한사항

• $1 ≤ n ≤ 100$

• $0 ≤ k ≤ N$

• $1 ≤ L[i] ≤ 10^4$

• $T[i] ∈ {0,1}$

---

💡 풀이 (언어 : Java)

얼마전 응시했던 기업의 코테에서 풀었던 문제와 유사한 정렬 문제이다. 그 문제는 몇가지 케이스만 맞고 풀이에 실패했다. 똑같은 HACKERRANK 문제였지만 그건 문제 정답 기준 설명이 불친절하고 지문도 지저분해 이해하는게 어려워 왜틀렸는지는 알 수가 없다. 반면에 이문제는 깔끔하고 쉬웠다. 기준 두가지로 배열을 정렬해야한다. 일단 T가 1인것을 앞으로 몰아주고, 그중에는 L이 큰 순으로 앞으로 오게 정렬해주면 된다. 그리고 이차원 배열을 순회하면서 T가 1인 원소를 만나면 K를 차감해주고 정답에 더해준다. 만약 K가 0이되면 T가 1인 원소를 만나면 정답에서 빼준다. 그리고 T가 0인 원소는 무조건 더해주는 알고리즘이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int luckBalance(int n, int k, int[][] arr) {
        int answer = 0;
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[1] == o2[1]) {
                return Integer.compare(o2[0], o1[0]);
            } else {
                return Integer.compare(o2[1], o1[1]);
            }
        });
        
        for (int i = 0; i < n; i++) {
            int standard = arr[i][1];
            if (k > 0 && standard == 1) {
                answer += arr[i][0];
                k--;
            } else if (standard == 1) {
                answer -= arr[i][0];
            } else {
                answer += arr[i][0];
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st2.nextToken());
            arr[i][1] = Integer.parseInt(st2.nextToken());
        }
        br.close();
        System.out.println(luckBalance(n, k, arr));
    }
}