[BAEKJOON] 23757 아이들과 선물 상자

문제 요약

• 알고리즘 분류: 힙, 우선순위 큐, 자료구조
• 난이도: Silver2
• 문제내용:
  • 선물N개와 아이들 M개가 있다.
  • 아이들은 순서대로 선물 N개 선택할수 있고 이전에 선택된 선물을 또 선택가능하다.
  • 아이들이 원하는 선물개수가 없는 경우 실망한다.
  • 아이들이 실망 하지 않고 선물을 다 가져  갈수 있는지 확인해라..

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

23757번: 아이들과 선물 상자

문제풀이

 이번 각 10^5개 데이터라서 O(NM)으로 풀면시간이 초과가 된다. 그래서 O(MlogN)이 나오도록 처리를 해야 한다. 그러기 위해서는 선물쪽에서 heap이라는 자료구조를 사용해서 풀어야 한다. 힙에 대한 자세한 설명은 여기에 참조하면된다.

 

문제 접근  방법

 이번 문제는 아이들은 순서대로 라서 입력 나온 그래로 실행 하면 되는데 선물 개수는 힙으로 정렬을 해야 한다. 그래서 매 순간 최대값이 나오도록 해야 하고 문제 에서는 선물 보다 아이들이 더 많아서 아이들이 선물을 들고가고 남은 선물은 힙에 다시 저장 해서 처리를 해야한다. 그러면 아이들이 순서대로 원하는것 만큼 들고 나오고 만약 원하는 개수가 없으면 루프에서 빠져 나오기만 하면 끝이다.

1. 아이들은 배열또는 리스트 선물을 최대힙으로 선언한다.
2. 아이들 차례마다 선물 최대값을 꺼내서 비교한 다음 아이들 원하는 개수가 선물 개수 보다 크면 루프에서 나온다.
3. 반대로 선물 개수가 더 크면 아이들은 선물 원하는 개수를 가져간다음 남는것은 다시 힙에 저장한다.

Code

Python

 파이썬은 힙라이브러리 heapq를 사용해서 처리하면된다.

import heapq

N, M = map(int, input().split())
presents = []
for present in list(map(int, input().split())):
    heapq.heappush(presents, -present)
children = list(map(int, input().split()))
flag = 1
for child in children:
    present = -heapq.heappop(presents)
    if child > present:
        flag = 0 
        break
    heapq.heappush(presents, child - present)
        
print(flag)

Java

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

public class Main {
	
	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 M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		PriorityQueue<Integer> presents = new PriorityQueue<Integer>();
		for(int i = 0; i < N; i++) {
			presents.offer(-1 * Integer.parseInt(st.nextToken()));
		}
		st = new StringTokenizer(br.readLine());
		int[] children = new int[M];
		for(int i  = 0; i < M; i++) {
			children[i] = Integer.parseInt(st.nextToken());
		}
		int present;
		int flag = 1;
		for(int child: children) {
			present = -1 * presents.poll();
			if(child > present) {
				flag = 0;
				break;
			}
			presents.offer(child - present);
		}
		
		System.out.println(flag);
	}
 
}