[Softeer][21년 재직자 대회예선] 마이크로서버

https://softeer.ai/practice/6264

Softeer - 현대자동차그룹 SW인재확보플랫폼

문제:

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

클러스터는 여러 대의 마이크로서버로 구성되어 있다. 각각의 마이크로서버는 정확히 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 이하이다.

입력형식
첫 번째 줄에 테스트 케이스의 개수 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를 사용하여서 조건을 만족한다.

 

접근법

투 포인터로 접근하는게 최선일것 같았다..!(조합최적?)

우선 정렬을 거친 후 조건을 확인, MIN이 300임으로 600이상인 서비스의 경우 모두 별도의 알고리즘 처리 없이 서버의 수를 1늘려준다. 

그리고 남은 서비스들에 관해 투포인터로 접근하여 while문을 내부에서 한번 더 돌려주었다. 

풀이 핵심 1: 600이상면 무조건 서버 배정(min이 300임으로)

틀린풀이(1차 접근)

def minimum_servers(test_cases):
    #for all test case 
    results = []
    for services in test_cases:
        # 먼저 서비스를 정렬
        services.sort()
        left, right = 0, len(services) - 1
        servers = 0
        # 투 포인터로 작은 서비스들과 큰 서비스들을 나눠서 배치
        while left <= right:
            # 600MiB 이상의 서비스는 큰 서비스부터 단독으로 배치
            if services[right] >= 600:
                servers += 1
                right -= 1
            else:
                sum_services = services[right]
                while sum_services + services[left] <= 900 and left <= right:
                    left += 1
                    sum_services = sum_services + services[left]
                    
                right -= 1
                servers += 1 
        results.append(servers)
    return results

# 입력 처리
T = int(input())  # 테스트 케이스 수
test_cases = []

for _ in range(T):
    N = int(input())  # 서비스 수
    services = list(map(int, input().split()))
    test_cases.append(services)

# 결과 계산 및 출력
results = minimum_servers(test_cases)
for res in results:
    print(res)

 

위와 같이 풀었을 때 공개된 case는 통과하였지만, 제출 시 통과하지 못했다..!

왜 그럴까..! 

예를 들어 300 300 300 450 450 인 경우가 있다면 모두 앞뒤로 짝을 이루는것보다 450, 450씩 짝을 짓는 것이 더 나은 선택지이기 때문이다! 

 

그럼 어떻게 접근해야할까?? 

아이디어 2: 300의 개수를 잘 세자

틀린풀이 2 300씩 3개를 먼저 묶을까..?

def minimum_servers(test_cases):
    results = []
    
    for services in test_cases:
        # 서비스를 오름차순으로 정렬
        services.sort()
        
        left, right = 0, len(services) - 1
        servers = 0
        
        # 300MiB 서비스를 먼저 처리
        num_300 = 0
        while left <= right and services[left] == 300:
            num_300 += 1
            left += 1

        # 300MiB 서비스는 3개씩 한 서버에 배치할 수 있음
        servers += num_300 // 3
        num_300_remainder = num_300 % 3
        left -= num_300_remainder

        # 600MiB 초과의 서비스는 단독 배치
        while left <= right and services[right] > 600:
            servers += 1
            right -= 1
        
        # 남은 서비스 처리 (600MiB 이하인 서비스들)
        while left < right:
            sum_services = services[right]
            while left < right and services[left] + sum_services <= 900:
                left += 1
                sum_services = sum_services       
            right -= 1
            servers += 1

        # 마지막으로 남은 서비스가 있으면 처리
        if left == right:
            servers += 1

        results.append(servers)
    
    return results

# 입력 처리
T = int(input())  # 테스트 케이스 수
test_cases = []

for _ in range(T):
    N = int(input())  # 서비스 수
    services = list(map(int, input().split()))
    test_cases.append(services)

# 결과 계산 및 출력
results = minimum_servers(test_cases)
for res in results:
    print(res)

 

틀림! 300 300 300 400 500 600 -> 300 300 300 / 400 / 500 / 600 이렇게 4개보다 300과 나머지로 짝을 이으면 3개만 필요 

 

최종 풀이 

아래 영상을 참고했다. 

https://www.youtube.com/watch?v=U6I5oFTFRIw

 

def minimum_servers(test_cases):
    results = []
    
    for services in test_cases:
        # 서비스를 오름차순으로 정렬
        services.sort()
        
        left, right = 0, len(services) - 1
        servers = 0
        


        # 600MiB 초과의 서비스는 단독 배치
        while left <= right and services[right] > 600:
            servers += 1
            right -= 1
            
        #600은 딱 300과만 match
        while left < right and services[left]==300 and services[right]==600:
            servers +=1
            left += 1
            right -= 1

        # 이후 남은 300MiB 서비스의 수를 세기
        num_300 = 0
        
        while left <= right and services[left] == 300:
            num_300 += 1
            left += 1
        
        # 남은 서비스 처리 (300~600사이 서비스들)
        while left < right:
            if services[left] + services[right] <= 900:
                left += 1
                right -= 1
                servers += 1
            elif num_300 >0:
                servers += 1
                num_300 -= 1
                right -= 1
            else:
                servers += 1
                right -= 1
                
        # 마지막으로 남은 서비스가 있으면 처리
        if left == right and services[left] != 300:
            servers += 1
            if num_300 >0:
                num_300 -= 1

        if num_300 > 0:
            servers += (num_300 + 2)//3
            
        num_300 = 0
            
        results.append(servers)
    
    return results

# 입력 처리
T = int(input())  # 테스트 케이스 수
test_cases = []

for _ in range(T):
    N = int(input())  # 서비스 수
    services = list(map(int, input().split()))
    test_cases.append(services)

# 결과 계산 및 출력
results = minimum_servers(test_cases)
for res in results:
    print(res)

 

결국은 300을 어떻게 처리하는가가 핵심인 문제였다. 

또 300은 여러가지로 조합이 가능하기에 큰 숫자들을 우선 처리하는것도 중요해던 구간을 나누는게 중요했던 문제였다...!