[코드트리] 코드트리 채점기 - Python

문제 링크

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-judger/description?page=1&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이 

heapq 사용해서 풀이 

도메인의 최대 개수가 300이기 때문에 도메인 기준으로 for문을 돌려야 시간초과를 피할 수 있음. 

 

필요한 변수 정의

# 채점 대기 큐에 있는 url set 
url_set = set()
# 채점 대기 큐에 있는 task 개수
task_num = 0
# 도메인 별로 채점 대기 heapq 관리 
# (우선순위, 들어온 시간, id)
waitQ = defaultdict(list)

n = 0
# key: domain, value: time 
# time에 domain을 채점할 수 있음 -> 부적절한 채점 확인을 위함  
stringLock = defaultdict(int)
# 채점가능한 채점기 저장할 heapq 
machineList =[]
# 채점기 별 채점 시작 시간, 채점 도메인 
machineStatus = []

 

(1) 코드트리 채점기 준비 

def build(data):
    global n, machineStatus
    
    n = int(data[1])
    url = data[2]
    # 가능한 채점기 리스트 추가 
    for i in range(1,n+1):
        heapq.heappush(machineList, i)
    
    # 채점기 개수만큼 초기화
    machineStatus = [ [] for _ in range(n+1)]
    
    # 대기 큐에 추가
    push_Q(0,1,url)

대기 큐에 push하는 함수는 아래와 같다. 

def push_Q(p_t, p_p, p_url):
    global task_num 
    
    # 대기 큐에 있는 url과 동일할 경우 추가하지 않음 
    if p_url in url_set:
        return 

    # 대기 큐 url 집합에 추가 
    url_set.add(p_url)
    
    domain, id = p_url.split('/')
    
    # 도메인 별 대기큐에 추가 
    heapq.heappush(waitQ[domain], (p_p, p_t, int(id)))
    # 대기큐에 있는 task 개수 증가 
    task_num +=1

(2) 채점 요청 

위에 대기큐에 Push 하는 함수 push_Q 실행 

 

(3) 채점 시도 

def try_check(data):
    t = int(data[1])

    # 채점 가능한 채점기가 없음 
    if len(machineList) == 0:
        return 
    
    best_prior = INF
    best_time = 0
    best_domain = ''
    best_id = 0 
    
    # 도메인 별로 체크 
    for p_d, que in waitQ.items():
        # 해당 도메인에 task 가 없음 
        if not que :
            continue 
        
        # 부적절한 채점 
        if stringLock[p_d] > t :
            continue 
        
        p_p, p_t, p_id = que[0]
        
        # 우선순위 작으면 갱신 
        if p_p < best_prior :
            best_prior = p_p 
            best_time = p_t
            best_domain = p_d 
            best_id = p_id 
        elif p_p == best_prior :
            # 우선순위 같고, 들어온 시간 작으면 갱신 
            if p_t < best_time :
                best_prior = p_p 
                best_time = p_t
                best_domain = p_d 
                best_id = p_id 
    
    # 채점 가능한 task가 없음 
    if best_prior == INF:
        return 

    # 채점할 채점기 하나 pop 
    m_index = heapq.heappop(machineList)
    # 해당 채점기가 채점하고 있는 task 정보 저장 
    machineStatus[m_index] = [t, best_domain]
    # 채전한 task 대기큐에서 pop 
    pop_Q(best_domain, best_id)
    # 해당 도메인 lock 걸기 -> 채점 불가능한 도메인 
    stringLock[best_domain] = INF

대기큐에서 Pop 하는 함수는 아래와 같다. 

def pop_Q(p_d, p_id):
    global task_num
    
    # 도메인에 있는 task 하나 pop
    heapq.heappop(waitQ[p_d])
    
    url = p_d + '/' + str(p_id) 
    # 대기큐에서 해당 url 제거
    url_set.remove(url)
    
    # 대기큐에 있는 task 개수 감소
    task_num -= 1

(4) 채점 종료 

def check_exit(data):
    t = int(data[1])
    c_index = int(data[2])
    
    # 채점기가 실행하고 있는 task가 없었음 
    if machineStatus[c_index] == [] :
        return 
    
    start_t, p_d = machineStatus[c_index]
    gap = t - start_t  
    # 채점가능한 시간 갱신 
    stringLock[p_d] = start_t + gap * 3 
    
    # 채점기가 실행하고 있는 task 정보 reset 
    machineStatus[c_index] = []
    
    # 채점 가능한 채점기에 추가 
    heapq.heappush(machineList, c_index)

(5) 채점 대기 큐 조회

task_num 출력

 

전체 코드는 아래와 같다. 

import heapq
from collections import defaultdict 
import sys 

INF = int(1e9)
si = sys.stdin.readline 

# 채점 대기 큐에 있는 url set 
url_set = set()
# 채점 대기 큐에 있는 task 개수
task_num = 0
# 도메인 별로 채점 대기 heapq 관리 
# (우선순위, 들어온 시간, id)
waitQ = defaultdict(list)

n = 0
# key: domain, value: time 
# time에 domain을 채점할 수 있음 -> 부적절한 채점 확인을 위함  
stringLock = defaultdict(int)
# 채점가능한 채점기 저장할 heapq 
machineList =[]
# 채점기 별 채점 시작 시간, 채점 도메인 
machineStatus = []

def push_Q(p_t, p_p, p_url):
    global task_num 
    
    # 대기 큐에 있는 url과 동일할 경우 추가하지 않음 
    if p_url in url_set:
        return 

    # 대기 큐 url 집합에 추가 
    url_set.add(p_url)
    
    domain, id = p_url.split('/')
    
    # 도메인 별 대기큐에 추가 
    heapq.heappush(waitQ[domain], (p_p, p_t, int(id)))
    # 대기큐에 있는 task 개수 증가 
    task_num +=1 
    
def pop_Q(p_d, p_id):
    global task_num
    
    # 도메인에 있는 task 하나 pop
    heapq.heappop(waitQ[p_d])
    
    url = p_d + '/' + str(p_id) 
    # 대기큐에서 해당 url 제거
    url_set.remove(url)
    
    # 대기큐에 있는 task 개수 감소
    task_num -= 1

def try_check(data):
    t = int(data[1])

    # 채점 가능한 채점기가 없음 
    if len(machineList) == 0:
        return 
    
    best_prior = INF
    best_time = 0
    best_domain = ''
    best_id = 0 
    
    # 도메인 별로 체크 
    for p_d, que in waitQ.items():
        # 해당 도메인에 task 가 없음 
        if not que :
            continue 
        
        # 부적절한 채점 
        if stringLock[p_d] > t :
            continue 
        
        p_p, p_t, p_id = que[0]
        
        # 우선순위 작으면 갱신 
        if p_p < best_prior :
            best_prior = p_p 
            best_time = p_t
            best_domain = p_d 
            best_id = p_id 
        elif p_p == best_prior :
            # 우선순위 같고, 들어온 시간 작으면 갱신 
            if p_t < best_time :
                best_prior = p_p 
                best_time = p_t
                best_domain = p_d 
                best_id = p_id 
    
    # 채점 가능한 task가 없음 
    if best_prior == INF:
        return 

    # 채점할 채점기 하나 pop 
    m_index = heapq.heappop(machineList)
    # 해당 채점기가 채점하고 있는 task 정보 저장 
    machineStatus[m_index] = [t, best_domain]
    # 채전한 task 대기큐에서 pop 
    pop_Q(best_domain, best_id)
    # 해당 도메인 lock 걸기 -> 채점 불가능한 도메인 
    stringLock[best_domain] = INF
    
def check_exit(data):
    t = int(data[1])
    c_index = int(data[2])
    
    # 채점기가 실행하고 있는 task가 없었음 
    if machineStatus[c_index] == [] :
        return 
    
    start_t, p_d = machineStatus[c_index]
    gap = t - start_t  
    # 채점가능한 시간 갱신 
    stringLock[p_d] = start_t + gap * 3 
    
    # 채점기가 실행하고 있는 task 정보 reset 
    machineStatus[c_index] = []
    
    # 채점 가능한 채점기에 추가 
    heapq.heappush(machineList, c_index)
    
def build(data):
    global n, machineStatus
    
    n = int(data[1])
    url = data[2]
    # 가능한 채점기 리스트 추가 
    for i in range(1,n+1):
        heapq.heappush(machineList, i)
    
    # 채점기 개수만큼 초기화
    machineStatus = [ [] for _ in range(n+1)]
    
    # 대기 큐에 추가
    push_Q(0,1,url)

q = int(si())

for _ in range(q):
    data =list(map(str,input().split()))
    q_type = int(data[0])
    
    if q_type == 100:
        build(data)    
    if q_type == 200 :
        push_Q(int(data[1]), int(data[2]), data[3])
    if q_type == 300:
        try_check(data)
    if q_type == 400 :
        check_exit(data)
    if q_type == 500:
        print(task_num)
    
    #print(url_set)
    #print(waitQ)
    #print(stringLock)
    #print(machineList)
    #print(machineStatus)
    #print(task_num)
    #print('------------------')