백준 13904번
https://www.acmicpc.net/problem/13904

문제

---

생각하기

---

• 그리디 정렬 문제이다.

• 우선순위 큐를 사용한다.

• 완전 탐색을 기반으로 하는 것 같다.

  • 배열의 모든 값을 탐색하고 가치가 낮은 것부터 버려서 높은 가치만 남게 하는 방식

동작

        int max = 0;
        Arrays.sort(tasks);
        PriorityQueue<Integer> pque = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            pque.offer(tasks[i].w);
            max += tasks[i].w;

            if (pque.size() > tasks[i].d) {
                max -= pque.poll();
            }
        }

PriorityQueue에는 Integer의 점수만을 넣어서 오름차순으로 정렬되도록 한다.

pque의 사이즈가 곧 일 수를 의미한다.

그래서 pque의 사이즈가 되는 동안 최고의 가치가 되는 것만 선택하면 된다.

다른 예시로는

4
2 7
2 5
1 20
1 10

순으로 되어있다고 하면 우선 정렬을 해준다.

1 순위 : 마감 날짜가 빠른 순
2 순위 : 날짜가 같을 때는 점수가 높은 순으로 정렬

{ [1, 20], [1, 10], [2, 7], [2, 5] }

이후 전체를 순회하면서 우선순위 큐에 모두 넣는 작업을 한다.

그리고 우선순위 큐에서 가치가 낮은 값들을 제거하면서 가치가 높은 값만 남기게 된다.

먼저 1 20을 넣고

다음은 1 10을 넣는다.

그리고 pque.size와 tasks[i].d를 비교하면 d가 size보다 작기 때문에 마감일을 초과한 것으로 보고 pque.poll()을 진행한다.

그리고 다음 2 7을 삽입하고 pque의 크기와 tasks[i].d가 일치하므로 pque.poll()을 하지 않는다.

이후 다시 반복으로 2 5는 제거되면 마지막으로pque에는 [1, 20], [2, 7]만 남게된다.

결과

코드

---

Java

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static Task[] tasks;

    private static class Task implements Comparable<Task> {
        int d;
        int w;

        private Task(int d, int w) {
            this.d = d;
            this.w = w;
        }

        @Override
        public int compareTo(Task o) {
            if (d == o.d) {
                return o.w - w;
            }
            return d - o.d;
        }
    } // End of Task class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int max = 0;
        Arrays.sort(tasks);
        PriorityQueue<Integer> pque = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            pque.offer(tasks[i].w);
            max += tasks[i].w;

            if (pque.size() > tasks[i].d) {
                max -= pque.poll();
            }
        }

        sb.append(max);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        tasks = new Task[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken()); // 마감일까지 남은 일수
            int w = Integer.parseInt(st.nextToken()); // 과제 점수

            tasks[i] = new Task(d, w);
        }

    } // End of input()
} // End of Main class

Kotlin

import java.io.BufferedReader
import java.io.File
import java.util.PriorityQueue
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private lateinit var tasks: Array<Task>

private data class Task(var d: Int, var w: Int) : Comparable<Task> {
    override fun compareTo(o: Task): Int {
        if (d == o.d) {
            return o.w - w
        }
        return d - o.d;
    }
}

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    tasks.sort()
    val pque = PriorityQueue<Int>()
    var max = 0

    for (i in 0 until N) {
        pque.offer(tasks[i].w)
        max += tasks[i].w

        if (pque.size > tasks[i].d) {
            max -= pque.poll();
        }
    }

    sb.append(max)
    return sb.toString()
} // End of solve()

private fun input() {
    N = br.readLine().toInt()

    tasks = Array(N) {
        val st = StringTokenizer(br.readLine())

        Task(
            st.nextToken().toInt(),
            st.nextToken().toInt()
        )
    }
} // End of input()