BinPacking_Softeer 마이크로서버

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

Softeer

제한시간 : C/C++(1초)/Java/JS/Python(3초)| 메모리 제한 : 1024MB

 

당신은 현대자동차그룹의 다양한 부서들이 사용하는 마이크로서비스들이 정상적으로 실행될 수 있도록 클러스터를 관리하는 업무를 맡고 있다.

클러스터는 여러 대의 마이크로서버로 구성되어 있다. 각각의 마이크로서버는 정확히 1000MiB의 메모리(RAM)를 갖고 있는데, 이 중 100MiB는 예비용으로 남겨 두기 때문에, 실제로 애플리케이션들이 사용할 수 있는 메모리는 총 900MiB이다.

하나의 마이크로서버에 여러 개의 마이크로서비스를 실행할 수 있는데, 이 때 마이크로서비스들이 사용하는 메모리의 총합은 900MiB를 넘을 수 없다.

현재 총 N개의 마이크로서비스가 실행 대기중이다. 이 중 i (1≤i≤N)번째 서비스는 정확히 mi MiB의 메모리를 요구한다. 각각의 서비스는 최소 300MiB, 최대 900MiB의 메모리만을 요구하고 있다.

모든 마이크로서비스들을 실행하기 위해 최소 몇 대의 마이크로서버가 필요한지 구하는 프로그램을 작성하라.

 

제약조건

• 주어지는 모든 수는 정수이다.
• 하나의 입력에서 1개 이상 1,000개 이하의 테스트 케이스를 해결해야 한다.
• 각각의 테스트 케이스에 대해:
  - 1≤N≤100,000
  - 모든 i (1≤i≤N)에 대해, 300≤mi≤900
• 하나의 입력에서 주어지는 모든 N의 합은 200,000 이하이다.

 

부분문제

• (10점) 모든 i (1≤i≤N)에 대해, mi=300
• (15점) 모든 i (1≤i≤N)에 대해, mi＞300
• (30점) 하나의 입력에서 주어지는 모든 N의 합은 5,000 이하이다.
• (45점) 추가 제약 조건 없음

 

입력형식

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
이후 아래와 같은 형식으로 2·T개의 줄에 T개의 테스트 케이스들이 주어진다.
이후 해당 케이스의 정보가 이어서 첫 번째 줄에 N이 주어진다. 두 번째 줄에 m1, m2,…, mN이 공백 하나씩을 사이로 두고 주어진다.

 

출력형식

각각의 테스트 케이스에 대해, 한 줄에 하나씩, 순서대로, 필요한 최소 마이크로서버의 수를 출력한다.

 

입력예제1

2
3
300 300 300
4
300 300 300 300

 

출력예제1

1
2

테스트 케이스 1: (서비스 1, 서비스 2, 서비스 3) 모두 한 서버에 두면 900MiB를 사용하므로 조건을 만족한다.
테스트 케이스 2: 두 대의 마이크로서버를 사서, (서비스 1, 서비스 2)를 한 서버에, (서비스 3, 서비스 4)를 다른 서버에 두면 각 서버에서 600MiB를 사용하므로 조건을 만족한다.

 

입력예제2

3
2
300 400
2
800 900
5
500 501 350 400 444

 

출력예제2

1
2
3

테스트 케이스 3: (서비스 1, 서비스 4), (서비스 2), (서비스 3, 서비스 5)를 각각 한 마이크로서버에서 실행하면, 각각 900MiB, 501MiB, 794MiB를 사용하여서 조건을 만족한다.

 

binary search/ DP/ DFS 로도 풀어봤지만 시간초과에서 에러가 나서 Treemap으로 해결하였습니다.

import java.util.*;
import java.io.*;


public class Main
{
   
    public static void main(String[] args) {
    

        Scanner sc = new Scanner(System.in);
        int c = 900;
        int N = sc.nextInt();
        for(int i = 0; i< N; i++){
            int t = sc.nextInt();
            Integer weight[] = new Integer[t];

            for(int j = 0; j < t ; j++){
                weight[j] = sc.nextInt();
            }
            System.out.println(firstFitDec(weight,weight.length,900));
        }
    }

    
    static int firstFit(Integer weight[], int n, int c)
    {
        int res = 0;

        TreeMap<Integer,Integer> bin_rem = new TreeMap<>();
        //아이템 개수만큼 실행
        for (int i = 0; i < n; i++)
        {
            int j;

               if(bin_rem.ceilingKey(weight[i]) != null && bin_rem.get(bin_rem.ceilingKey(weight[i])) > 0){ // 담을 서버가 있으면


                    //메모리를 사용한 서버를 한대 줄이고
                   int leftcnt = bin_rem.get(bin_rem.ceilingKey(weight[i])) -1;
                   int key = bin_rem.ceilingKey(weight[i]);
                   if(leftcnt == 0)
                      bin_rem.remove(key);
                   else
                       bin_rem.put(key,bin_rem.get(key) -1);

                    //해당 메모리가 남은 서버를 하나 별도로 추가한다.
                    bin_rem.put(key - weight[i], bin_rem.getOrDefault(key  - weight[i],0) + 1);

                }else{ // 없으면 새로운 서버 생성 남은 메모리가 중복값이 있을 수도 있음
                    bin_rem.put(c - weight[i], bin_rem.getOrDefault(c - weight[i],0) + 1);
                }

        }
        int ans = 0;

        for (int s: bin_rem.values()) {
           ans+=s;
        }
        return ans;
    }
    static int firstFitDec(Integer weight[], int n, int c)
    {

        Arrays.sort(weight, Collections.reverseOrder());
        return firstFit(weight, n, c);
    }
}