728x90
https://softeer.ai/practice/info.do?idx=1&eid=628&sw_prbl_sbms_sn=157452
💡 문제 풀이
투포인터(?) 문제이다.
요청의 크기가 300 ~ 900이고 서버는 900을 넘어가면 안 되기 때문에 결국 3가지 경우로 나뉜다.
- 한 서비스가 600을 넘어가는 경우. 다른 서비스를 추가할 수 없어서 서버 하나를 준다.
- 300짜리 서비스가 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))
'문제 풀이 > 소프티어 (Softeer)' 카테고리의 다른 글
[Python] 소프티어 : 플레이페어 암호 (1) | 2023.03.05 |
---|---|
[Python] 소프티어 : 징검다리 (0) | 2023.03.05 |
[Python] 소프티어 : 거리 합 구하기 (0) | 2023.02.20 |
[Python] 소프티어 : 이미지 프로세싱 (0) | 2023.02.20 |
[Python] 소프티어 : 로드 밸런서 트래픽 예측 (0) | 2023.02.19 |
댓글