[Python] 소프티어 : 로드 밸런서 트래픽 예측

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

Softeer

---

💡 문제 풀이

구현 문제이다.

노드에 접근하는 순서가 존재하고 존재에 맞춰서 요청을 처리해 주면 된다.

 

1000건의 요청이 들어왔고, 루트 밸런서에 3, 5, 6번 밸런서가 연결되어 있으면

각 밸런서에 공통적으로 1000 // 3건 만큼 요청을 수행할 것이고 순서대로 진행되야 하니

1000 % 3 만큼 각 노드에 순서대로 1만큼 추가해 주면 된다.

✔️ 느낀 점

문제가 이해 안 가서 오래 걸렸고 중간에 순서가 있다는 걸 알아채지 못해서 시간을 많이 소비하였다.

그냥 재귀적으로 풀면 무조건 시간초과가 발생하므로 라운드-로빈에 대해서 조금 생각해 보면 쉽게 풀 수 있다.

💻 코드 (마지막이 풀이)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
requests = [0] * (n + 1)
balancer = {}

for i in range(n):
    tmp = list(map(int, input().split()))
    
    if len(tmp) > 1: 
        balancer[i+1] = ([0, tmp[0], tmp[1:]])

def dfs(idx):
    requests[idx] += 1
    
    if idx in balancer:
        b = balancer[idx]

        next = b[2][b[0] % b[1]]
        balancer[idx][0] += 1
        
        dfs(next)
        
    return

def run():
    for _ in range(k):
        dfs(1)
    
    print(' '.join(map(str, requests[1:])))

run()

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
requests = [0] * (n + 1)
requests[1] = k

balancer = {}
for i in range(n):
    tmp = list(map(int, input().split()))
    
    if len(tmp) > 1: 
        balancer[i+1] = [tmp[0], tmp[1:]]

for i in balancer.keys():
    total = requests[i]
    
    for j in balancer[i][1]:
        requests[j] += (total // balancer[i][0])
        
    for idx, k in enumerate(balancer[i][1], start=1):
        if idx > total % balancer[i][0]: break
        requests[k] += 1

print(' '.join(map(str, requests[1:])))

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
requests = [0] * (n + 1)

balancer = {}
for i in range(n):
    tmp = list(map(int, input().split()))
    
    if len(tmp) > 1: 
        balancer[i+1] = [tmp[0], tmp[1:]]

def dfs(index, request):
    requests[index] += request
    
    if index in balancer:
        totalRequest = requests[index]
        nextNodes = balancer[index][0]
        
        for i, nextNode in enumerate(balancer[index][1], start= 1):
            nextRequest = totalRequest // nextNodes
            if i <= totalRequest % nextNodes:
                nextRequest += 1
            dfs(nextNode, nextRequest)
            
    return
    
dfs(1, k)

print(' '.join(map(str, requests[1:])))

import sys, collections
input = sys.stdin.readline

n, k = map(int, input().split())

balancer = collections.defaultdict(list)
for i in range(1, n+1):
    tmp = list(map(int, input().split()))
    if len(tmp) > 1: balancer[i] = tmp[1:]

def getOrder(n):
    indegree = [0] * (n+1)
    
    for k, nodes in balancer.items():
        for n in nodes:
            indegree[n] += 1
            
    q = [1]
    order = []
    
    while q:
        i = q.pop(0)
        order += i,
        
        for node in balancer[i]:
            indegree[node] -= 1
            if indegree[node] == 0:
                q += node,
                
    return order

def runServer(order):
    requests = collections.defaultdict(int)
    requests[1] = k
    
    for node in order:
        nextNodes = len(balancer[node])
        if nextNodes == 0: continue
        
        totalRequest = requests[node]
        for i, nextNode in enumerate(balancer[node], start= 1):
            nextRequest = totalRequest // nextNodes
            
            if i <= totalRequest % nextNodes:
                nextRequest += 1
                
            requests[nextNode] += nextRequest
    
    return requests
        
order = getOrder(n)
requests = runServer(order)

requests = sorted(requests.items(), key=lambda x:x[0])
requests = [v for k, v in requests]
print(' '.join(map(str, requests)))