[백준] 1781 - 컵라면 (JAVA)

개츠비·2023년 4월 1일

목록 보기

48/84

소요시간 : 47분
문제 사이트 : 백준
문제 수준 : 골드 2
문제 유형 : 자료 구조, 그리디 알고리즘, 우선순위 큐
다른 사람의 풀이를 참고 했는가 ? : X
한 번 풀었다가 다시 푸는 문제인가 ? : X
문제 링크 : https://www.acmicpc.net/problem/1781
푼 날짜 : 2023.04.01

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘, 정렬, 우선순위 큐를 사용

2. 사고과정

처음에는 우선순위 큐만 사용해서 풀어보려고 했었다.
예제 입력까지는 통과했으나 제출했을 때 틀렸다고 나왔고
우선순위 큐와 정렬을 함께 사용해야겠다고 생각했다.
우선순위 큐와 정렬을 함께 사용한 적은 딱 1번 있는데
https://www.acmicpc.net/problem/1202 의 문제를 풀었을 때다.
당시 이 문제는 스스로 풀지 못해서 다른 사람의 풀이를 보고 참고했었다.

결국 우선순위 큐와 정렬을 함께 사용했고, 정답.

여기서의 소요시간은 47분인데 5일전에
한번 풀려고 20-30분 정도 썼을 때 못풀었었으니까
사실 상 1시간 넘게 걸린 것 같다.

3. 풀이과정

라면들을 정렬 ( 데드라인 날짜가 큰 순서대로. 즉 날짜 역순으로 정렬한다. )
우선순위 큐 선언. 우선순위 큐의 기준은
(1) 컵라면 수가 많은 것, (2) 날짜가 큰 순서대로
그리고 N이 200,000까지 이므로 200,000 일 째부터 1일씩 낮춰가면서 데드라인이 현재 날짜에 해당하는 모든 라면들을 pq에 넣음.
만약 현재 pq가 비었다면 해당 날짜에 풀 수 있는 문제가 없는 것임. continue
만약 pq가 비지 않았다면 pq의 정렬기준은 컵라면 수가 많은 것이 우선시이므로 sum에 더해준다. 그러므로 최적해임을 보장받을 수 있다.

예제 입력을 보면
(1) 200,000 부터 7일째 까지는 계속 continue 된다.
(2) 6일 째에 컵라면 수 1개인 문제가 등장. pq에 이 값을 넣고
이제 pq에서 poll 하여서 6일 째에 컵라면 1개짜리 문제를 푼다.
(3) 5일 째에는 continue
(4) 4일 쨰에는 continue
(5) 3일 째에는 pq에 라면 2개짜리 문제, 1개짜리 문제가 들어온다.
poll되는 것은 라면이 더 많은 2개짜리 문제이고 이 문제를 푼다
(6) 2일 째에는 pq에 4개짜리 문제, 5개 짜리 문제가 추가로 들어온다. 그리고 3일째의 1개짜리 문제도 아직 남아있다.
poll되는 것은 라면이 가장 많은 5개짜리 문제
(7) 1일 째에는 6개짜리 문제, 7개짜리 문제가 추가로 들어온다.
그리고 2일째의 4개짜리 문제, 3일째의 1개짜리 문제도 남아있다.
poll 되는 것은 가장 라면이 많은 7개짜리 문제

=> output : 15

이 문제의 시간 복잡도를 계산해보자면 라면들을 정렬하는 데에 O(NlogN)
pq에 최대 200,000개 add 되는 데에 O(NlogN)
pq에서 최대 200,000 개 poll 되는 데에 O(NlogN) 이 걸린다.
그러므로 시간 복잡도는 O(NlogN).

4. 소스코드

import java.util.*;
import java.io.*;
class Ramen implements Comparable <Ramen> {
	int deadline;
	int ramen;
	Ramen(int deadline,int ramen) {
		this.deadline=deadline;
		this.ramen=ramen;
	}
	@Override
	public int compareTo (Ramen o) {
		if(this.ramen<o.ramen)
			return 1;
		else if(this.ramen==o.ramen) {
			if(this.deadline>o.deadline)
				return 1;
			else if(this.deadline==o.deadline)
				return 0;
		}
		return -1;
	}
	
}
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N=Integer.parseInt(br.readLine());
		Ramen ramen[]=new Ramen[N];
		for(int i=0;i<ramen.length;i++) {
			st=new StringTokenizer(br.readLine());
			int n1=Integer.parseInt(st.nextToken());
			int n2=Integer.parseInt(st.nextToken());
			ramen[i]=new Ramen(n1,n2);
		}
		Arrays.sort(ramen,new Comparator<>() {
			@Override
			public int compare(Ramen o1,Ramen o2) {
				if(o1.deadline<o2.deadline)
					return 1;
				else if(o1.deadline==o2.deadline)
					return 0;
				else 
					return -1;
			}
		});
		
		PriorityQueue<Ramen> pq=new PriorityQueue<>();
		
		int cnt=0;
		int sum=0;
		for(int i=200000;i>=1;i--) {
			while(cnt<ramen.length&&ramen[cnt].deadline==i) {
				pq.add(ramen[cnt++]);
			}
			
			if(pq.isEmpty()) continue;	
			
			sum+=pq.poll().ramen;
		}
		
		System.out.println(sum);
		

	}
}