[코드트리] : 코드트리 채점기

url : https://www.codetree.ai/problems/codetree-judger/description
유형 : simulation, Priority Queue

import heapq as hq
import copy
Q = int(input())
waiting = {}
judging = {}
history = {}
waiting_domain = set()
judging_domain = set()
checker = []
N = 0
def input_waiting_queue(priorty, time, url):
    durl = url.split('/')[0]
    if durl in waiting:
        set_ = waiting[durl]
        hq.heappush(set_, [priorty, time, url])
        waiting[durl] = set_
    else:
        waiting[durl] = [[priorty, time, url]]
    waiting_domain.add(url)

def first(list_):
    global N
    global checker
    N = int(list_[1])
    checker = [i for i in range(N)]
    u = list_[2]
    input_waiting_queue(1, 0, u)

def second(list_):
    t = int(list_[1])
    # 우선순위
    p = int(list_[2])
    u = list_[3]
    if u in waiting_domain:
        return
    input_waiting_queue(p, t, u)

def judge_queue(now):
    final_priorty = 10**10
    final_time = 10**10
    final_url = ""
    for durl in waiting:
        # 채점중인 도메인
        if durl in judging_domain: continue
        # history 체크
        if durl in history:
            s, e = history[durl]
            gap = e - s
            # 채점 불가
            if now < s + 3 * gap:
                continue
        p,t,url = hq.heappop(waiting[durl])
        # 우선순위 빠름
        if final_priorty > p:
            final_priorty = p
            final_time = t
            final_url = durl
        elif final_priorty == p and final_time > t:
            final_priorty = p
            final_time = t
            final_url = durl
        input_waiting_queue(p, t, url)
    # 결정됨
    if final_url != "":
        p,t,url = hq.heappop(waiting[final_url])
        if len(waiting[final_url]) == 0:
            del waiting[final_url]
        j = hq.heappop(checker)
        judging[j] = [now, final_url]
        waiting_domain.remove(url)
        judging_domain.add(final_url)

def third(list_):
    t = int(list_[1])
    if len(checker) > 0:
        judge_queue(t)


def fourth(list_):
    t = int(list_[1])
    j = int(list_[2]) - 1
    if j in judging:
        # 종료
        [start, du] = judging[j]
        del judging[j]
        judging_domain.remove(du)
        hq.heappush(checker, j)
        history[du] = [start, t]

def fifth(list_):
    t = int(list_[1])
    cnt = 0
    for w in waiting:
        cnt += len(waiting[w])
    print(cnt)

for i in range(Q):
    list_ = list(input().split())
    if list_[0] == '100':
        first(list_)
    elif list_[0] == '200':
        second(list_)
    elif list_[0] == '300':
        third(list_)
    elif list_[0] == '400':
        fourth(list_)
    elif list_[0] == '500':
        fifth(list_)

후기

• 문제설명만 잘 파악하면 쉽게 풀었을 것 같은 문제
• 조건이 꽤 복잡해서 잘 정리하는 게 필요
  • 특히 도메인인지, url전체인지 구분잘하기
• 각각 모듈화 하는 것이 필수
• 시간초과 발생 > 개발 전 생각하기
  • 도메인의 수가 300개밖에 안된다는 점이 key point
  • 따라서 반복문을 돌아도 괜찮았음
  • 구분이 priority queue로 되어있길래 당연히 우선순위기반으로 heap에 넣어서 뽑으려 했으나 시간초과 -> 따라서 dictionary로 key는 도메인으로 하고, value를 heap으로 해서 반복문 돌면서 적절한 문제를 뽑았다.
• 정말 많이 틀려서 화가 났긴 한데..(그래도 백준과 달리 등수 안깎여서 조타b) 끝까지 답 안본 나 칭찬해~