[Python] 소프티어 : 마이크로서버

https://softeer.ai/practice/info.do?idx=1&eid=628&sw_prbl_sbms_sn=157452 

Softeer

---

💡 문제 풀이

투포인터(?) 문제이다.

 

요청의 크기가 300 ~ 900이고 서버는 900을 넘어가면 안 되기 때문에 결국 3가지 경우로 나뉜다.

1. 한 서비스가 600을 넘어가는 경우. 다른 서비스를 추가할 수 없어서 서버 하나를 준다.
2. 300짜리 서비스가 3개 들어오는 경우.
3. 그 외 두 서비스가 900이하의 메모리를 잡아먹는 경우

따라서 투 포인터를 따라가면서 계산해주면 된다.

✔️ 느낀 점

처음에 deque를 이용해서 조건문으로 해결하려고 했다. 하지만 25점짜리 풀이었고 오답을 절대로 찾을 수가 없었다.

투포인터를 생각하고 양쪽 끝에서 접근시켜 풀었다. 시간복잡도는 O(n)이 나온다.

💻 코드

import sys
from collections import deque
input = sys.stdin.readline

CUT = 450
MIN = 600
MAX = 900

def getServers(requests):
    dq = deque(sorted(requests))
    cnt = 0
    
    while dq:
        if len(dq) >= 2:
            a = dq.popleft()
            b = dq.pop()
            sum_ = a + b
            
            if MIN < sum_ <= MAX:
                cnt += 1
            elif sum_ == MIN:
                dq.append(sum_)
            elif sum_ > MAX:
                if a > CUT: cnt += 1
                else: dq.appendleft(a)
                    
                if b > CUT: cnt += 1
                else: dq.append(b)
        else:
            dq.popleft()
            cnt += 1
        
    return cnt

t = int(input())

for _ in range(t):
    n = int(input())
    requests = list(map(int, input().split()))

    print(getServers(requests))

import sys
input = sys.stdin.readline

def getServers(n, requests):
    requests = sorted(requests)
    server = 0
    
    smallest = 0
    for request in requests:
        if request > 300: break
        smallest += 1
    
    start = smallest
    end = n-1
    
    while start <= end:
        server += 1
        
        # 큰 값이 600이 넘는 경우
        if requests[end] > 600: pass
        
        # 양쪽 값의 합이 900이하인 경우
        elif start != end and requests[start] + requests[end] <= 900:
            start += 1
        
        # 양쪽 값의 합이 600인 경우
        elif smallest > 0: # 
            smallest -= 1
        end -= 1
    
    # 남아있는 300을 처리
    server += (smallest+2)//3

    return server
    
t = int(input())

for _ in range(t):
    n = int(input())
    requests = list(map(int, input().split()))

    print(getServers(n, requests))