[코드트리][기출문제] 코드트리 채점기

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

코드트리 채점기

자료구조 및 알고리즘

• dictionary, set, heap

문제 풀이 및 회고

문제가 좀 헷갈리게 써져 있는듯(나만 그런가… 제공되는 테스트 케이스가 더 있었으면 좋았을텐데). 문제 좀 명확히 읽고 제출하자 귀찮아서 코드 if name == “main” 안했음 ㅋㄷㅋㄷ

코드(python)

from collections import defaultdict
import heapq as hq

def setting(command: list):
    """
    N개의 채점지. 초기 문제 url에 해당하는 u0. 문제에서의 url = domain/문제ID
    domain은 알파벳 소문자와 .으로만 이루어져있고
    ID는 1 ~ 10억이하 정수값
    N개의 채점기에는 1번부터 N번까지 번호가 붙어있고, 0초에 채점 우선순위가 1이면서 url이 u0인 초기 문제에 대한 채점 요청이 들어오게 됩니다.
    채점 task는 채점 대기 큐에 들어가게 됩니다.
    """
    global waiting_queue, waiting_url, machines, next_machine_num

    N, u = int(command[1]), command[2]

    machines = [[] for _ in range(N+1)]
    next_machine_num = [i for i in range(1, N+1)]

    domain, problem_ID = u.split('/')
    hq.heappush(waiting_queue[domain], [1, 0, u]) # t초에 채점 우선순위가 p이면서 url이 u인 문제에 대한 채점 요청
    waiting_url.add(u) # url 대기 (중복 확인 위한)

    return None


def request(command: list): # 200 t p u
    """
    채점 요청. t초에 채점 우선순위가 p이면서 url이 u인 문제에 대한 채점 요청
    채점 task는 채점 대기 큐에 들어감.
    단, 채점 대기 큐에 있는 task 중 정확히 u와 일치하는 url이 단 하나라도 존재하면 큐에 추가하지 않고 넘어감
    """
    global waiting_queue, waiting_url, machines, history

    t, p, u = int(command[1]), int(command[2]), command[3]

    if u in waiting_url: # 단, 채점 대기 큐에 있는 task 중 정확히 u와 일치하는 url이 단 하나라도 존재하면 큐에 추가하지 않고 넘어감
        return None
    
    domain, problem_ID = u.split('/')
    hq.heappush(waiting_queue[domain], [p, t, u]) # t초에 채점 우선순위가 p이면서 url이 u인 문제에 대한 채점 요청
    waiting_url.add(u) # url 대기 (중복 확인 위한)
    return None


def try_request(command: list): # 300 t
    """
    t초에 채점 대기 큐에서 즉시 채점이 불가능한 경우를 제외하고 남은 task 중 우선순위가 가장 높은 채점 task를 골라 채점 진행

    task가 채점이 될 수 없는 조건.
    1. 해당 task 도메인이 현재 채점을 진행중인 도메인 중 하나라면 불가능
    2. 해당 task의 도메인이 정확히 일치하는 도메인에 대해 가장 최근에 진행된 채점 시작 시간이 start, 종료 시간이 start + gap였고
    현재 시간 t가 start + 3*gap보다 작다면, 부적절한 채점이라 의심되기에 채점이 불가합니다.

    즉시 채점이 가능한 경우 중 우선순위가 가장 높은 채점 task는 아래 조건을 따라 골라짐.
    1. 채점 우선순위가 p의 번호가 작을수록 우선순위가 높음
    2. 만약 채점 우선순위가 동일하다면 채점 task가 채점 대기 큐에 들어온 시간이 더 빠를수록 우선순위가 높음
    
    채점 가능한 task가 하나라도 있다면 쉬고 있는 채점기 중 가장 번호가 작은 채점기가 우선순위가 가장 높은 task에 대한 채점을 시작.
    쉬는 채점기가 없으면 요청을 무시하고 넘어감
    """
    global waiting_queue, waiting_url, machines, history, doing_domain
    t = int(command[1])

    if len(next_machine_num) == 0 or len(waiting_url) == 0: # 쉬는 채점기가 없거나 채점 대기큐에 아무것도 없음. 요청을 무시하고 넘어감
        return None # 요청을 무시하고 넘어감


    # domain 별로 heap 만들어잇!
    candidates = []

    for k, v in waiting_queue.items(): #[domain] = [p, t, u]
        if k in doing_domain: # 1. 해당 task 도메인이 현재 채점을 진행중인 도메인 중 하나라면 불가능
            continue 

        if t < 3 * history[k][1] - 2 * history[k][0]: # 2. 부적절한 채점
            continue
        
        if v != []: # 해당 domain에 가능한 task가 있음
            priority, time, url = v[0] 
            hq.heappush(candidates, [priority, time, k])
        
    if len(candidates) == 0: # 채점이 가능한 task가 없음
        return None
    
    priority, time, domain = candidates[0] # 실행할 task

    _, _, url = hq.heappop(waiting_queue[domain]) # 실행하는 task domain 하나 제거
    
    machines[hq.heappop(next_machine_num)] = [url, t] # url, 시작 시간(t)
    doing_domain.add(domain) # 도메인 시작
    waiting_url.discard(url) # 채점할 수 있음

    return None


def end_request(command: list): # 400 t J_id
    """
    t초에 J_id번 채점기가 진행하던 채점이 종료. J_id 채점기는 다시 쉬는 상태가 됨.
    만약 J_id 채점기가 진행하던 채점이 없었다면 이 명령은 무시됨.
    """
    global waiting_queue, waiting_url, machines, next_machine_num, history
    t, J_id = int(command[1]), int(command[2])

    if machines[J_id] == []: # 만약 J_id 채점기가 진행하던 채점이 없었다면 이 명령은 무시됨.
        return None
    
    url, start_time = machines[J_id] # J_id 채점기 정보
    domain, problem_ID = url.split('/')

    machines[J_id] = [] # J_id 채점기 다시 쉬는 상태
    hq.heappush(next_machine_num, J_id) # J_id 채점기는 이제 다시 채점할 수 있음
    history[domain] = [start_time, t] # 시작시간, 끝나는 시간 history에 저장
    doing_domain.discard(domain) # 도메인 끝

    return None

def check_queue(command: list): # 500 t
    """
    시간 t에 대기 큐에 있는 채점 task의 수를 출력
    """
    global waiting_queue

    print(len(waiting_url))
    return None


def show_info():
    global waiting_queue, waiting_url, next_machine_num, machines, history, doing_domain

    print("waiting_queue : ", waiting_queue)
    print("waiting_url : ", waiting_url)
    print("next_machine_num : ", next_machine_num)
    print("machines : ", machines[1:])
    print("history : ", history)
    print("domain : ", doing_domain)
    return None


waiting_queue = defaultdict(lambda: []) # waiting_queue[domain] = [] 정렬
waiting_url = set() #waiting_queue에 있는 url들
next_machine_num = []
machines = [] # [J_id] = 작업
history = defaultdict(lambda: [0,0]) # [url] = [시작 시간, 종료 시간]
doing_domain = set() # 진행중인 도메인

if __name__ == "__main__":
    Q = int(input())

    setting(input().split())
    
    stop = -1
    for ith in range(2, Q+1):
        command = input().split()
        
        if command[0] == '200':
            request(command)
        elif command[0] == '300':
            try_request(command)
        elif command[0] == '400':
            end_request(command)
        else: # 500 t
            check_queue(command)
        
        if ith == stop:
            print("now command : ", command)
            show_info()
            break