[BAEKJOON]1781 컵라면

문제 요약

• 알고리즘 분류: 그리디, 정렬, 힙
• 난이도:Gold2
• 문제내용:
  • 문제 번호, 데드라인, 컵라면이 있다.
  • 문제푸는 시간이 1이고 데드라인안에 풀어야 한다.
  • 위 조건대로 컵라면 최대 받을수 있는 개수를 출력해라.

• 사이트: https://www.acmicpc.net/problem/1781

1781번: 컵라면

문제풀이

 이번 문제는 그리디와 힙 문제인데, 그리디 알고리즘은 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디와 힙에 대한 설명은 밑에 사이트에 참조하면된다.

그리디: https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

힙: https://jih3508.tistory.com/81

문제 접근 방법

 이번문제를 보면 데이터가 최대 20만개이다. 그러면 시간 복잡도로 O(NlogN)안으로 풀어야 한다. 일단 어떻게 풀 예정이라면 데드라인 기준으로 정렬해서 데이터하나씩 heap에 다가 저장한다음 데드라인이 heap에 저장된 개수보다 클 경우 heap에서 가장 작을값을 빼는 형식으로 보면 된다.

 예제 문제로 예시로 보면 일단 정렬하면 아래 그림 처럼 나올것이다.

 그 다음 데이터 하나씩 저장하고 힙에 저장된 개수와 데드라인을 비교하면서 진행하면된다.

 위 표는 저장하는 과정을 표로 나타 낸것이다.

i = 1

1번째는 저장하고 데드라인 1개와 저장한 개수가 같기 때문에 넘어간다.

i = 2

 2번째도 저장하고 데드라인이랑 비교해보니까 힙에 저장한 개수가 데드라인보다 크다. 그래서 1개를 지워야하는데 그중 가장 작은 값이 6이기 때문에 6을 지운다.

 

i = 3

3번째는 힙에 저장하고 데드라인 개수랑 같기 때문에 넘어간다.

 

i = 4

4번째도 저장하고 데드라인이랑 비교해보니까 힙에 저장한 개수가 데드라인보다 크다. 그래서 1개를 지워야하는데 그중 가장 작은 값이 4이기 때문에 4를 지운다.

 

i = 5

5번째는 힙에 저장하고 데드라인 개수랑 같기 때문에 넘어간다.

 

i = 6

6번째도 저장하고 데드라인이랑 비교해보니까 힙에 저장한 개수가 데드라인보다 크다. 그래서 1개를 지워야하는데 그중 가장 작은 값이 1이기 때문에 1을 지운다.

 

i = 7

7번째는 힙에 저장하고 데드라인 개수보다 작기때문에 넘어간다.

 

문제를 다 풀었고 컵라면 개수를 합치면 15개가 나온다.

 

정리

1. 데드라인 기준으로 정렬한다.
2. 정렬한 데이터를 하나씩 꺼내서 힙에 저장한다.
3. 저장할때 저장된 개수와 데드라인 비교해서 저장된 개수가 데드라인 보다 크면 데드라인까지 작은 값을 지운다.
4. 연산이 다 끝나면 더한다.

Code

Python

import sys
import heapq
input = sys.stdin.readline

N = int(input())

array = []
for _ in range(N):
   array.append(list(map(int, input().split())))
   
array.sort()
heap = []
for count, number in array:
   heapq.heappush(heap, number)
   if count < len(heap):
      heapq.heappop(heap)
      
print(sum(heap))

Java

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

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] array = new int[N][2];
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			array[i][0] = Integer.parseInt(st.nextToken());
			array[i][1] = Integer.parseInt(st.nextToken());	
		}
		Arrays.sort(array, (x, y) -> {
			if(x[0] == y[0]) {
				return Integer.compare(x[1], y[1]);
			}else {
				return Integer.compare(x[0], y[0]);
			}
		});
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		for(int i = 0; i < N; i++) {
			heap.add(array[i][1]);
			if(array[i][0] < heap.size()) {
				heap.poll();
			}
		}
		System.out.println(heap.stream().reduce(0, (a, b) -> a + b));

	}
	
}