[Baekjoon] 11270_Disastrous Downtime

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

---

< Disastrous Downtime >

 

문제 풀이 

 

요청 발생 시간을 정렬하여 앞에서부터 가능한 만큼 같은 서버에서 처리하도록 한다.

 

 3 2
1000
1010
1999

주어진 예제가 위와 같다면 1000, 1010을 같은 서버에서 처리하고 1999를 다른 서버에서 처리해 총 2개의 서버가 필요하게 된다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _11270_ { // Disastrous Downtime

	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 k = Integer.parseInt(st.nextToken());

		ArrayList<Integer> list = new ArrayList<>();
		Queue<int[]> queue = new LinkedList<>();

		int num[] = new int[n];
		for (int i = 0; i < n; i++) {
			num[i] = Integer.parseInt(bf.readLine());
		}
		Arrays.sort(num);

		list.add(0);

		for (int i = 0; i < n; i++) {
			boolean flag = false;

			if (list.get(list.size() - 1) < k) {
				list.set(list.size() - 1, list.get(list.size() - 1) + 1);
				queue.add(new int[] { num[i], list.size() - 1 });
				flag = true;
			} else if (queue.peek()[0] + 1000 <= num[i]) {
				int temp[] = queue.poll();
				queue.add(new int[] { num[i], temp[1] });
				flag = true;
			}

			if (!flag) {
				list.add(1);
				queue.add(new int[] { num[i], list.size() - 1 });
			}
		}
		System.out.println(list.size());
	}

}

변수)
n, k : 요청 개수, 최대 요청 처리 가능한 개수
list : 각 서버당 처리하고 있는 요청 개수
queue : 요청 끝났는지 확인하기 위한 Queue

 

요청 개수와 최대 요청 처리 가능한 개수를 입력받는다. 요청 개수만큼 요청을 입력받아 배열에 저장한 후 오름차순으로 정렬한다. 요청을 살펴보며 서버에 아직 자리가 남아있다면 추가하고, 자리가 없다면 맨 처음 요청이 끝났는지 확인 후 끝났다면 그 서버에 추가한다. 둘 다 해당되지 않는다면 새로운 서버를 추가한다. 

 

최종 list의 size를 출력한다.  

---

---