Softeer <마이크로서버>

Softeer <마이크로서버>

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=628&sw_prbl_sbms_sn=57818 

Softeer

 

마이크로서버

ㅌ

 

 

 

문제 해결

쉬울 줄 알고 풀었는데 어려웠다... (처음에 서비스가 최소 300mib인 것을 간과했다...)

2-pointer를 이용하여 풀었다. 

 

하나의 마이크로 서버를 사용하는 경우는 아래와 같다.

1. 600 이상의 값 -> 하나의 마이크로 서버 (서비스가 필요로 하는 메모리의 최소 값이 300이기 때문에)
2. 300 + 600 -> 하나의 마이크로 서버
3. 300 + a -> 하나의 마이크로 서버 (a는 600보다 작다.)
4. a + b가 900보다 작거나 같을 경우 -> 하나의 마이크로 서버

서비스가 필요로 하는 메모리들의 리스트 service를 일단 정렬한다.

start = 0, end = 리스트의 크기 -1 이다.

 

1번의 경우를 체크하기 위해 end를 -1씩 하면서 600보다 큰 경우를 모두 카운트한다.

2번의 경우도 카운트한다.

3번의 경우를 체크하기 위해 먼저 300의 개수 cnt300을 카운트한다.

service[start] + service[end]의 값이 900보다 작거나 같을 경우는 4번의 경우로 카운트 한다.

service[start] + service[end]의 값이 900보다 클 경우에 cnt300이 0보다 크다면 service[end]의 값과 300으로 구성된 3번의 경우가 된다. 만약 cnt300의 값이 0이라면 service[end]의 값은 혼자 마이크로서버를 사용해야 한다.

 

300이 3개가 모이면 하나의 마이크로 서버를 사용할 수 있으므로 cnt300/3의 값을 answer에 더해준다. 만약 나머지 값이 존재한다면 answer에 1을 더한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testcase = Integer.parseInt(br.readLine());
		for (int i = 0; i < testcase; i++) {
			int n = Integer.parseInt(br.readLine());
			String[] inArr = br.readLine().split(" ");
			int[] service = new int[n];
			for (int j = 0; j < n; j++) {
				service[j] = Integer.parseInt(inArr[j]);
			}
			Arrays.sort(service);
			System.out.println(micro_server(0, n - 1, service));
		}

	}

	public static int micro_server(int start, int end, int[] service) {
		int answer = 0;
		while (service[end] > 600) {
			answer++;
			end--;
			if (end < 0) {
				break;
			}
		}
		while (start < end && service[start] == 300 && service[end] == 600) {
			answer++;
			start++;
			end--;
		}
		int cnt300 = 0;
		while (start <= end && service[start] == 300) {
			cnt300++;
			start++;
		}
		while (start < end) {
			if (service[start] + service[end] <= 900) {
				answer++;
				start++;
				end--;
			}
		}
		answer += cnt300 / 2;
		if (cnt300 % 2 == 1) {
			answer++;
		}
}