[Baekjoon] 23843_콘센트

Gold V

문제(출처: https://www.acmicpc.net/problem/23843)

---

< 콘센트 >

 

문제 풀이 

 

값이 큰 것을 우선으로 하는 우선순위 큐 A에 충전에 필요한 시간을 저장한다.(=충전 시간이 많은 순대로 정렬)

값이 작은 것을 우선으로 하는 우선순위 큐 B에 A를 콘센트 개수만큼 넣어준다.

충전 시간을 계산해 준다. 

 

 

 my solution (Java)

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

public class _23843_ { // 콘센트

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(bf.readLine());
		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			queue.add(Integer.parseInt(st.nextToken()));
		}

		PriorityQueue<Integer> socket = new PriorityQueue<>();
		ArrayList<Integer> list = new ArrayList<>();
		int result = 0, num=0;
		while (!queue.isEmpty()) {
			if (socket.size() < m) {
				socket.add(queue.poll());
			} else {
				num=socket.poll();
				result += num;
				while(!socket.isEmpty()) {
					int x =socket.poll()-num;
					if(x>0) {
						list.add(x);
					}
				}
				for(int i=0; i<list.size(); i++) {
					socket.add(list.get(i));
				}
				list.clear();
			}
		}

		while(!socket.isEmpty()) {
			num=socket.poll();
		}
		result+=num;

		System.out.println(result);
	}
}

 

Main

변수)
n : 전자기기의 개수
m : 콘센트 개수
queue : PriorityQueue <Integer> 충전에 필요한 시간 저장 (내림차순)
socket : PriorityQueue <Integer> 콘센트 (오름차순)
result : 충전에 필요한 최소 시간
num : 값 저장하는 변수

 

- 전자기기의 개수(n), 콘센트 개수(m) 입력

- 충전에 필요한 시간 n개를 입력받아 queue에 저장

- queue가 빌 때까지 반복

: socket의 크기가 콘센트의 개수(m) 보다 작다면 충전할 수 있으므로 queue에서 poll 해서 socket에 저장

: socket의 크기가 콘센트 개수라면 socket에서 값을 poll 해서 충전시킴

: 충전시키면 socket에 있던 나머지 전자기기도 그만큼 충전돼야 하므로 다 poll 해서 앞에서 충전한 만큼 빼서 다시 socket에 저장

- 마지막에 충전되는 전자기기는 socket의 마지막 값이 최댓값이므로 다 poll 한 후 마지막 값만 result에 더함

- 충전에 필요한 최소 시간(result) 출력

---

---