[코드트리/삼성SW역량테스트] 코드트리 채점기 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/codetree-judger

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

 

Status : Solved

 

Time : 01:16:59

 

---

 

문제 설명 / 입력 및 출력

 

전체 문제 설명은 코드트리 사이트를 참조해 주세요!

 

---

 

풀이

 

우선순위 큐를 이용하는 게 좋다. 채점 대기열(우선순위, 들어온 순서 순으로 우선도를 가진다) 및 채점기(채점기 번호가 낮을 수록 우선순위를 가진다) 모두 빈번히 호출될 수 있으며 우선도 순으로 항상 출입이 가능해야 한다.

 

또한 url의 존재 여부를 자주 확인해야 하므로 set 자료형을 사용하도록 하자. 여부를 O(1)시간 내에 판단할 수 있다.

 

또한, 쿼리가 300일때, 즉 '풀이 가능한 문제를 뽑아 채점기에 할당하기'를 주의깁게 풀이하는 게 좋다. 하나의 채점 대기열을 사용하게 되면 한 쿼리에 최대 O(NlogN)의 시간복잡도로 처리(즉 채점 대기열에서 가장 먼저 채점 가능한 문제가 나올 때까지 pop하고, 이외의 문제를 전부 push해야 함)하게 되므로 시간초과를 겪는다.

다행히 문제에서 주어진 도메인 수는 최대 300개임을 명시했으므로, 도메인별로 다른 채점 대기열을 사용하는 방식을 추천한다. 풀이 가능한 문제의 조건을 같은 도메인마다 공유하게 되므로 훨씬 빠른 속도로 쿼리를 처리할 수 있다. 

 

이외에는 어떤 도메인/url이냐에 따른 채점 여부를 결정하는 세팅을 제대로 구현하면 된다(여기서 맞왜틀이 많이 나오게 되는 것 같다..)

 

 

풀이 코드

from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline
MAX = float('inf')

Q = int(input())
querys = [input().split() for _ in range(Q)]
grading_domain = dict()
prev_ended_domain = dict()
domains = set()
waited_task = dict()
waited_url = set()
tot_waited = 0

for i in range(Q) :
    query, *body = querys[i]
    if query <= '200' :
        domain = body[-1].split('/')[0]
        domains.add(domain)
        grading_domain[domain] = False
        prev_ended_domain[domain] = -1
        if domain not in waited_task :
            waited_task[domain] = list()

_, N, u0 = querys[0]
d0 = u0.split('/')[0]
graders = [(-1,-1) for _ in range(int(N))]
empty_graders = list(range(int(N)))
heapify(empty_graders)
heappush(waited_task[d0], (1, 0, u0))
waited_url.add(u0)
tot_waited += 1

for i in range(1, Q) :
    query, *body = querys[i]
    if query == '200' :
        t, p, u = body
        d = u.split('/')[0]
        if u in waited_url :
            continue
        waited_url.add(u)
        heappush(waited_task[d], (int(p), int(t), u))
        tot_waited += 1
    elif query == '300' :
        if not empty_graders or not tot_waited:
            continue
        t = int(body[0])
        target_d, priority, target_u = '', (MAX, MAX), ''
        for d in domains :
            if grading_domain[d] or prev_ended_domain[d] > t or not waited_task[d]:
                continue
            tp, tt, tu = waited_task[d][0]
            if priority <= (tp, tt) :
                continue
            target_d, priority, target_u = d, (tp, tt), tu

        if priority < (MAX, MAX) :
            idx = heappop(empty_graders)
            grading_domain[target_d] = True
            waited_url.discard(target_u)
            graders[idx] = (t, target_d)
            heappop(waited_task[target_d])
            tot_waited -= 1

    elif query == '400' :
        t, idx = map(int, body)
        idx -= 1
        if graders[idx] == (-1, -1) :
            continue
        s, d = graders[idx]
        graders[idx] = (-1, -1)
        grading_domain[d] = False
        prev_ended_domain[d] = s + (t - s)*3
        heappush(empty_graders, idx)
    else :
        print(tot_waited)

풀이 완료!