[백준] 2109번 '순회강연' - Java

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 20232KB | 시간 316ms | 코드 길이 1289B

import java.io.*;
import java.util.*;

class Req {
	int p, d;
	
	public Req(int p, int d) {
		this.p = p;
		this.d = d;
	}
}

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		int n = Integer.parseInt(bf.readLine());
		
		PriorityQueue<Req> pq = new PriorityQueue<>((o1, o2) -> {
			if(o1.p == o2.p) return o1.d - o2.d;
			return o2.p - o1.p;
		});
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int tmp_p = Integer.parseInt(st.nextToken());
			int tmp_d = Integer.parseInt(st.nextToken());
			
			pq.add(new Req(tmp_p, tmp_d));
		}
		
		int ans = 0;
		boolean[] scheduled = new boolean[10001];
		while(!pq.isEmpty()) {
            Req cur = pq.poll();
            
            for(int i = cur.d ; i > 0 ; --i) {
                if(!scheduled[i]) {
                    scheduled[i] = true;
                    ans += cur.p;
                    break;
                }
            }
        }
        bw.write(Integer.toString(ans));
        
        bf.close();
        bw.flush();
        bw.close();
	}
}

 

PriorityQueue<Req> pq = new PriorityQueue<>((o1, o2) -> {
			if(o1.p == o2.p) return o1.d - o2.d;
			return o2.p - o1.p;
		});

이 코드를 통해 d필드가 낮을수록, p필드가 높을수록 높은 우선순위를 갖도록 하였습니다.

 

while(!pq.isEmpty()) {
            Req cur = pq.poll();
            
            for(int i = cur.d ; i > 0 ; --i) {
                if(!scheduled[i]) {
                    scheduled[i] = true;
                    ans += cur.p;
                    break;
                }
            }
        }

큐에서 하나씩 빼가며 scheduled 배열의 빈곳에 넣는 코드입니다.

---

Search 🔍

https://velog.io/@jh5253/%EB%B0%B1%EC%A4%80-2109-%EC%88%9C%ED%9A%8C%EA%B0%95%EC%97%B0-Java%EC%9E%90%EB%B0%94