Coding 공부

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()

def solution():
    priority_que = []
    for num in range(1,N+1):
        if not indegree[num]:
            priority_que.append(num)
    heapq.heapify(priority_que)

    result = []
    while priority_que:
        num = heapq.heappop(priority_que)
        result.append(num)
        for next_num in graph[num]:
            indegree[next_num] -= 1
            if not indegree[next_num]:
                heapq.heappush(priority_que,next_num)
    return result

N,M = map(int,input().split())

graph = [ [] for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    indegree[y] += 1

print(*solution())

문제를 읽어보면 순서가 정해져있고, 앞선 문제를 풀어야지 뒤의 문제를 풀 수 있다고 되어 있다.

이 문구를 보고 위상정렬임을 알 수 있고, 위상정렬 해주면 된다.

문제 난이도가 골드2 이지만, 골드2 수준은 아닌 듯한 문제였다. queue 대신 heapq를 쓰면 풀리는 문제라,

위상 정렬에 대해 알고 있으면 쉽게 풀릴 수 있는 문제라 생각한다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split())



INF = float('inf')
step_trash = [[INF for _ in range(M)] for _ in range(N)]
arround_trash = [[INF for _ in range(M)] for _ in range(N)]

arround_trash_can = [[0 for _ in range(M)] for _ in range(N)]


arr = []
start = []
flower = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'S':
            start = (x,y)
        elif temp[y] == 'F':
            flower = (x,y)
    
    arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]


for x in range(N):
    for y in range(M):
        if arr[x][y] == 'g':
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        arround_trash_can[nx][ny] = 1

node_list = []

heapq.heappush(node_list,(0,0,start[0],start[1]))

step_trash[start[0]][start[1]] = 0
arround_trash[start[0]][start[1]] = 0
visited = [[True for _ in range(M)] for _ in range(N)]

while node_list:
    s_t,p_t,x,y = heapq.heappop(node_list)

    if not visited[x][y]:
        continue
    visited[x][y] = False


    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] == 'g':
                if step_trash[nx][ny] > s_t + 1:
                    step_trash[nx][ny] = s_t + 1
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny], arround_trash[nx][ny], nx, ny))
            else:
                if step_trash[nx][ny] > s_t:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
                elif step_trash[nx][ny] == s_t and arround_trash[nx][ny] > p_t + arround_trash_can[nx][ny]:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] =  p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))






x,y = flower

print(step_trash[x][y] , arround_trash[x][y])

이 문제를 지문을 이해하는데 어려움을 겪었던 문제였다. 

문제를 제대로 읽어야하는데 빈 공간을 갈때 주변의 쓰레기 개수와 상관없이 1개이든 4개이든 1번의 불쾌함으로 측정을 해야한다.

그러므로 이 점을 주의해서 우선순위를 설정을 해서 다익스트라를 해줘야한다.

다익스트라를 돌리기전에 사전 작업을 했는데, 쓰레기인 구역을 찾아서

그 주변에 빈공간이 있으면 arround_trash_can라는 배열에 1로 표시를 해줬다.

그래서 arround_trash_can이라는 배열에 0이 아닌 1이 표시된 부분은 쓰레기가 존재하는 옆칸을 지나가는 것이다.

이 문제에서 형택의 여자친구는 쓰레기를 지나가는 것을 가장 싫어하고, 쓰레기 옆을 지나가는 것을 두번째로 싫어한다고 되어있다.

그러므로 heapq에 우선순위를 쓰레기를 지나가는 것 s_t를 가장 앞에 두었고, 쓰레기 옆을 지나가는 개수인 p_t를 두번째 인자로 넣어주었다.

이렇게 한뒤 형택이 상하좌우로 움직이면서 쓰레기인 칸을 밟았을때에는 step_trash의 값과 비교를 해서 더 낮은 값이면, 갱신을 하고 넣어주었다.

그리고 빈공간일때에는 먼저 쓰레기를 밟는 개수가 더 작은 경우인지 확인을 한 뒤, 더 작으면 값을 갱신하고 heapq에 넣어준다.

근데 그게 아니라 쓰레기를 밟는 개수는 동일하다면, 쓰레기 옆을 지나간 횟수를 비교를 해서 heapq에 넣어준다.

이 문제에서 주의해야했던 점은 쓰레기 옆을 지나가는 유무를 구분하는 것이지, 빈공간 옆의 쓰레기의 개수를 세는

것이 아니였던 점이다.

import sys
import heapq

from collections import defaultdict
input = sys.stdin.readline
class Algorithm():
    def __init__(self,num):
        self.num = num
        self.min_heap = []
        self.max_heap = []
    def insert(self,pb_num,diff):
        heapq.heappush(self.min_heap,(diff,pb_num))
        heapq.heappush(self.max_heap,(-diff,-pb_num))
    def find_heap(self,flag):
        result = []
        if flag > 0:
            if self.max_heap:
                while (-self.max_heap[0][1] not in number_set) or number_algo[-self.max_heap[0][1]][0] != self.num or number_algo[-self.max_heap[0][1]][1] != -self.max_heap[0][0]:
                    heapq.heappop(self.max_heap)
                    if not self.max_heap:
                        break
            if self.max_heap:
                result = [-self.max_heap[0][0],-self.max_heap[0][1]]
        else:
            if self.min_heap:
                while (self.min_heap[0][1] not in number_set) or number_algo[self.min_heap[0][1]][0] != self.num or number_algo[self.min_heap[0][1]][1] != self.min_heap[0][0]:
                    heapq.heappop(self.min_heap)
                    if not self.min_heap:
                        break
            if self.min_heap:
                result = self.min_heap[0]
        return result


class Difficulty():
    def __init__(self,num):
        self.num = num
        self.min_heap = []
        self.max_heap = []

    def insert(self,pb_num):
        heapq.heappush(self.min_heap,pb_num)
        heapq.heappush(self.max_heap,-pb_num)
    def find_heap(self,x):
        result = []
        if x > 0:
            if self.min_heap:
                while self.min_heap[0] not in number_set or (number_algo[self.min_heap[0]][1]) != self.num:
                    heapq.heappop(self.min_heap)
                    if not self.min_heap:
                        break
            if self.min_heap:
                result = self.min_heap[0]

        else:
            if self.max_heap:
                while -self.max_heap[0] not in number_set or (number_algo[-self.max_heap[0]][1]) != self.num:
                    heapq.heappop(self.max_heap)
                    if not self.max_heap:
                        break
            if self.max_heap:
                result = -self.max_heap[0]
        return result


N = int(input())
algo_set = set()
diff_set = set()
algo_dict = {}
diff_dict = {}
number_algo = {}
number_set = set()
for _ in range(N):
    number,dif,algo = map(int,input().split())
    if algo not in algo_set:
        algo_dict[algo] = Algorithm(algo)
        algo_set.add(algo)
    if dif not in diff_set:
        diff_dict[dif] = Difficulty(dif)
        diff_set.add(dif)
    algo_dict[algo].insert(number,dif)
    diff_dict[dif].insert(number)
    number_algo[number] = [algo,dif]
    number_set.add(number)


M = int(input())

for i in range(M):
    command,*arg = input().split()
    if command == 'recommend':
        G,x = map(int,arg)
        print(algo_dict[G].find_heap(x)[1])
    elif command == 'recommend2':
        x = int(arg[0])
        diff_check = 0 if x == 1 else float('inf')
        pb_num_check = -1
        for algo_num in algo_dict:
            ch = algo_dict[algo_num].find_heap(x)
            if not ch: continue
            if x == 1:
                if ch[0] >diff_check:
                    diff_check = ch[0]
                    pb_num_check = ch[1]
                elif ch[0] == diff_check:
                    if pb_num_check < ch[1]:
                        pb_num_check = ch[1]
            else:
                if ch[0] < diff_check:
                    diff_check = ch[0]
                    pb_num_check = ch[1]
                elif ch[0] == diff_check:
                    if pb_num_check > ch[1]:
                        pb_num_check = ch[1]
        print(pb_num_check)
    elif command == 'recommend3':
        flag,L_num = map(int,arg)
        result = -1
        if flag == -1:
            L_num = L_num + flag
        while 0<=L_num<=100:
            if L_num in diff_set:
                ch = diff_dict[L_num].find_heap(flag)
                if not ch:
                    L_num = L_num + flag
                    continue
                result = ch
                print(ch)
                break
            L_num = L_num + flag
        if result == -1:
            print(-1)

    elif command == 'solved':
        pb_num = int(arg[0])
        number_set.remove(pb_num)
        del number_algo[pb_num]
    else:
        pb_num,diff_num,algo_num = map(int,arg)
        if algo_num not in algo_set:
            algo_dict[algo_num] = Algorithm(algo_num)
            algo_set.add(algo_num)
        if diff_num not in diff_set:
            diff_dict[diff_num] = Difficulty(diff_num)
            diff_set.add(diff_num)
        algo_dict[algo_num].insert(pb_num,diff_num)
        diff_dict[diff_num].insert(pb_num)
        number_algo[pb_num] = [algo_num,diff_num]
        number_set.add(pb_num)

이 문제는 추천 방식이 총 3개이다.

첫번째 추천은 알고리즘 G에서 가장 난이도와 높은것과 낮은것

두번째 추천은 모든 알고리즘에서 가장 난이도가 높은것과 낮은것

세번째 추천은 주어진 난이도에서 가장 가까운 난이도의 문제를 추천이다.

그래서 나는 크게 2가지의 클래스를 만들어주었다.

각 클래스는 각각 max_heap과 min_heap을 만들어주었는데.

이리 한 이유는 세번째 추천과 , 첫번째추천, 두번째 추천이 flag에 따라 동일한 조건일때 반환해야하는 문제의 조건이 달랐기 때문이다.

각각 max_heap과 min_heap, 그리고 알고리즘 클래스는 알고리즘 번호 난이도 클래스는 난이도 번호를 저장시켜주었다.

그러면 추천이 들어올때마다 while문을 도려서 현재, heap에서 사라져야할 문제들에 대해서, 제거를 해주고,

남은 heap일떄 출력을 해주는 방식으로 했다.

그리고 2번째와 3번째는 난이도와 알고리즘 분류는 최대 100이기 때문에 전체탐색을 해주었다.

좀 더 자세하게 설명하면 2번째 추천은 전체 탐색

3번째 추천은 탐색을 하면서, 0과 100을 넘어갔는데도 만족하는 조건을 못 찾으면 -1을 출력하게 해주었다.

min_heap과 max_heap 그리고 남아있는 문제들에 대한 상태관리를 해야하기 때문에 코드가 길고 복잡했다.

import sys
from collections import defaultdict

input = sys.stdin.readline
const_value = 100000
N = int(input())
re1_dict = defaultdict(dict)
re2_dict = defaultdict(dict)
re3_dict = defaultdict(dict)
problem_dict = dict()
for _ in range(N):
    p_num,l_num,g_num = map(int,input().split())
    calc_num = l_num*const_value + p_num-1
    re1_dict[g_num][calc_num] = 1
    re2_dict[calc_num] = 1
    re3_dict[l_num][p_num] = 1
    problem_dict[p_num] = [l_num,g_num]


M = int(input())
for _ in range(M):
    command,*arg = input().split()

    if command == 'recommend':
        g_num,x = map(int,arg)
        if x > 0:
            calc_num = max( re1_dict[g_num].keys())
        else:
            calc_num = min(re1_dict[g_num].keys())
        l_num = calc_num//const_value
        p_num = calc_num%const_value + 1
        print(p_num)
    elif command == 'recommend2':
        x = int(arg[0])
        if x > 0:
            calc_num = max(re2_dict.keys())
        else:
            calc_num = min(re2_dict.keys())
        l_num = calc_num//const_value
        p_num = calc_num%const_value + 1
        print(p_num)
    elif command == 'recommend3':
        x,find_L_num = map(int,arg)
        if x < 0:
            find_L_num = find_L_num + x
        result = -1
        while 0<=find_L_num<=100:
            if re3_dict.get(find_L_num):
                if x>0:
                    result = min(re3_dict[find_L_num].keys())
                else:
                    result = max(re3_dict[find_L_num].keys())
                break
            find_L_num = find_L_num + x
        print(result)
                
    elif command == 'solved':
        p_num = int(arg[0])
        l_num,g_num = problem_dict[p_num]
        calc_num = l_num*100000 + p_num-1
        del re3_dict[l_num][p_num]
        del re2_dict[calc_num]
        del re1_dict[g_num][calc_num]
    else:
        p_num,l_num,g_num = map(int,arg)
        calc_num = l_num*100000 + p_num-1
        re1_dict[g_num][calc_num] = 1
        re2_dict[calc_num] = 1
        re3_dict[l_num][p_num] = 1
        problem_dict[p_num] = [l_num,g_num]

 두번째 방식은 실행 시간을 포기하는 것이다.

실행시간을 포기하고, 딕셔너리를 통해 추천을 해주는 것이다.

그러면 어떻게 해야할것인가 궁금할 것이다.

3번쨰 추천은 문제번호만 상관하면되기때문에 문제번호를 그대로 넣어주면 된다.

하지만 첫번째와 두번째 추천은

문제 난이도가 동일할시 문제번호의 대소를 구분해주어야한다.

문제에서 주어진 문제번호의 범위는 1~100000이다. 그리고 난이도의 범위는 1~100이다.

그러면 

난이도 * 100000 + (문제번호 -1)을 해주면 한 숫자로 이 문제의 정보를 저장할 수 있다고 생각했다.

난이도가 가장 큰 값이기 때문에, 먼저 앞의 난이도를 비교해주고 앞의 2~3자리가 동일하면 나머지 문제번호를

통해 대소관계를 알수 있을거라 생각했다.

그래서 첫번째, 두번째 추천에는 이 계산된 값을 키 값으로하여, 딕셔너리를 만들어주고,

추천이 들어올때마다 min,max를 통해 원하는 값을 추출해주었다.

추출하는 방법도 간단하게 100000으로 나눈 몫이 난이도이고, 나머지에 +1을 해준 것이 문제번호이다.

그리고 solved를 해줄때에도

위의 공식을 이용해서 문제번호와 난이도를 계산해서 그 키 값을 제거해주는 된다.

대신 시간차가 많이 나는 방식이니, 시간을 줄이고 싶으신분은 min_heap과 max_heap을

어차피 통과만 되면 된다는 분들은 후자의 방법을 사용해도 될것이다.

import sys
input = sys.stdin.readline

N = int(input())


problem_dict = {}
re1_dict = {}

for _ in range(N):
    pb_num,l_num = map(int,input().split())
    re1_dict[(l_num,pb_num)] = 1
    problem_dict[pb_num] = l_num


M = int(input())

for _ in range(M):
    command,*arg = input().split()

    if command == 'add':
        pb_num,l_num = map(int,arg)
        problem_dict[pb_num] = l_num
        re1_dict[(l_num,pb_num)] = 1
    elif command == 'recommend':
        flag = int(arg[0])
        if flag > 0:
            keys = max(re1_dict.keys())
        else:
            keys = min(re1_dict.keys())
        print(keys[1])
    else:
        pb_num = int(arg[0])
        l_num = problem_dict[pb_num]
        del problem_dict[pb_num]
        del re1_dict[(l_num,pb_num)]

 이 문제를 풀때 사실 boj.kr/21944 번을 먼저 풀었기 때문에 그 때 시도했던 후자 방식을 먼저 적용시켜보았다.

제한 시간내에 동작은 하지만 위 풀이는 추천하지 않는다.

문제를 푸는 아이디어는 다음과 같다. 어차피 우리는 recommend를 해야하고, 그때의 값들을 관리하는 것이다.

그러면 이 문제를 풀때 dictinory를 이용하기로 했다.

(난이도, 문제번호)를 key 값으로 하는 dictionary를 만들어준 뒤 

recommend를 해줄때 1일때에는 최대값

-1일때는 최소값을 구해서 출력해주는 식으로 했다.

max,min이 알아서 앞에서부터 비교를 해주니 가능한 방식이다.

그리고 문제를 풀었을 때에는

problem_dict 이라는 dictionary에 문제번호와 난이도를 매핑시켜준 딕셔너리가 있다.

그러면 problem_dict에서 solved 된 문제번호를 통해 난이도를 가져오고,

re1_dict의 값을 제거해주면 된다.

import sys
import heapq
input = sys.stdin.readline

def recommend(flag,heap):
    flag = -flag
    while heap and (heap[0][1]*flag not in problem_dict.keys() or problem_dict[heap[0][1]*flag] != heap[0][0]*flag):
        heapq.heappop(heap)
    result =heap[0]
    result = result[1]*flag
    return result

N = int(input())
max_heap = []
min_heap = []
problem_dict = {}
for _ in range(N):
    pb_num,l_num = map(int,input().split())
    max_heap.append((-l_num,-pb_num))
    min_heap.append((l_num,pb_num))

    problem_dict[pb_num] = l_num
heapq.heapify(max_heap)
heapq.heapify(min_heap)
M = int(input())

for _ in range(M):
    command,*arg = input().split()
    if command == 'add':
        pb_num,l_num = map(int,arg)
        heapq.heappush(max_heap,(-l_num,-pb_num))
        heapq.heappush(min_heap,(l_num,pb_num))
        problem_dict[pb_num] = l_num
    elif command == 'solved':
        pb_num = int(arg[0])
        del problem_dict[pb_num]
    else:
        flag = int(arg[0])
        if flag > 0:
            print(recommend(flag,max_heap))
        else:
            print(recommend(flag,min_heap))

이게 정석적인 풀이이다.

min_heap 과 max_heap을 이용해서 풀었다.

여기서 주의해야할점은 problem_dict을 활용해 사라진 문제들을 찾아서, 제거를 해주어야한다.

while문을 통해 없는 문제들은 전부 없애주고, while문을 탈출했을때 heap[0]에 있는 값을 return 해주면 된다.

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []
init_list = [list(map(int,input().split())) for _ in range(N)]

init_list.sort()
result = [0 for _ in range(100001)]
INF = float('inf')
for start_time,end_time in init_list:
    if heap:
        if heap[0] <= start_time:
            heapq.heappop(heap)
        heapq.heappush(heap,end_time)
    else:
        heapq.heappush(heap,end_time)
total_cnt = len(heap)
print(total_cnt)

check_number = []
min_chair_number = []
for start_time,end_time in init_list:
    if check_number:
        while check_number and check_number[0][0] <= start_time:
            _,pop_idx = heapq.heappop(check_number)
            heapq.heappush(min_chair_number,pop_idx)
        if not min_chair_number:
            idx = len(check_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
        else:
            idx = heapq.heappop(min_chair_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
    else:
        result[0] += 1
        heapq.heappush(check_number,(end_time,0))
print(*result[:total_cnt])

첫번째 풀이는 다음과 같다.

먼저 전체 컴퓨터의 개수를 구해준다.

check_number에는 끝시간과 사용하고 있는 사람이 있는 컴퓨터의 index를 넣어준다.

그리고 시작시간보다. 끝나는시간이 먼저 끝났을때에는 그걸 min_chair_number에 빈 컴퓨터의 index를 넣어준다.

만약 이미 들어차있는 check_number에 현재 시작시간보다 작은것이 하나도 없다하면,

먼저 min_chair_number가 있으면 min_chair_number에서 빈자리를 꺼내서 check_number에 넣어준다.

그리고 min_chair_number가 없으면 현재 주어진 컴퓨터에서 전부 자리가 꽉찬거이므로, 새 컴퓨터를 발급해주고,

그 값을 check_number에 넣어주면 된다.

import sys
import heapq
input = sys.stdin.readline
N = int(input())
time_list = []
for i in range(N):
    start_time,end_time = map(int,input().split())
    heapq.heappush(time_list,(start_time,i))
    heapq.heappush(time_list,(end_time,i))
isSeatperson = [-1]*N
seat_info = []
com_idx = 0
min_com_list = []

while time_list:
    _,person_number = heapq.heappop(time_list)

    if isSeatperson[person_number] == -1:
        if min_com_list:
            isSeatperson[person_number] = heapq.heappop(min_com_list)
        else:
            isSeatperson[person_number] = com_idx
            com_idx += 1
    else:
        heapq.heappush(min_com_list,isSeatperson[person_number])
        seat_info.append(isSeatperson[person_number])


max_com = max(seat_info)+1

result = [0]*max_com

for com_number in seat_info:
    result[com_number] += 1

print(max_com)
print(*result)

좀 더 깔끔한 풀이는 다음과 같다.

시작시간과 끝시간을 두개로 나눠서 time_list에 넣어준다.

그리고 난뒤에 하나씩 꺼내주면서, 만약에 이 사람이 앉을때 즉 start_time일때에는 min_com_list에 남은게 있으면,

하나를 출력해서 배정을 시켜준다.

그리고 그게 아니면 새로운 컴을 발급시켜주고, 그때의 idx를 증가시켜준다.

그리고 퇴실할때 나간 사람의 자리를 넣어준다.

그리고 마지막으로 그 사람이 앉았던 자리 정보를 seat_info에 저장시켜준다.

이렇게 전체 자리수를 구하고, seat_info를 통해 각 자리마다 앉았던 사람들의 정보를 저장시켜준다.

import sys
input = sys.stdin.readline
INF = (10**12)+1

def get_process(mid_priority):
    global N
    if dp.get(mid_priority):
        return dp[mid_priority]
    else:
        total_process_cnt = 0


        for i in range(N):
            process = arr[i]

            if mid_priority<=process.sp:
                total_process_cnt += process.time
            elif process.sp< mid_priority<=process.ep:
                total_process_cnt = total_process_cnt + process.ep - mid_priority +1
        
        dp[mid_priority] = total_process_cnt
        return total_process_cnt


def b_search(target_T):
    left = 0
    right = INF*2
    while left<=right:
        mid = (left+right)//2
        total_cnt = get_process(mid)
        if total_cnt>=target_T:
            next_priority_cnt = get_process(mid+1)
            if next_priority_cnt<target_T:
                remain_priority_cnt = target_T - next_priority_cnt
                for i in range(N):
                    if arr[i].sp <= mid <=arr[i].ep:
                        remain_priority_cnt -= 1
                        if remain_priority_cnt == 0:
                            result.append(arr[i].process_id)
                            break
                break
            else:
                left = mid + 1

        else:
            right = mid-1


class Process:
    def __init__(self,_id,_spend_time,_init_priority):
        self.process_id = _id
        self.time = _spend_time
        self.ep = _init_priority+INF
        self.sp = _init_priority+INF-spend_time+1


Q,N = map(int,input().split())
arr = []
for _ in range(N):
    process_id,spend_time,init_priority = map(int,input().split())
    new_process = Process(process_id,spend_time,init_priority)
    arr.append(new_process)
dp = {}
arr.sort(key=lambda x : x.process_id)
result = []

for _ in range(Q):
    find_time = int(input())

    b_search(find_time)


for i in range(Q):
    sys.stdout.write(str(result[i])+'\n')

이 문제 또한 앞선 문제와 같이 혼자서 풀기 어려운 난이도라, https://github.com/cdog-gh/gh_coding_test 해설을 보고 푼 문제이다.

이 문제는 boj.kr/21773 과 boj.kr/21777 문제를 이해해야지만 풀 수 있는 문제였다.

앞서 21777에서 말한것처럼  초기 priority가 P라 하고, 총 실행시간이 T라한다면,

P~ (P-T+1) 까지 우선순위를 실행하게 될 것이다.

그러므로 우리는 무지하게 큰 초기값을 각각의 priorty에 더해준다. 왜냐하면, 양수의 priority로만 구분을 해주기 위함이다.

그러므로 INF + P 를 end_priority 그리고 INF + P - T + 1 를 start_priority 로 해주었다.

근데 숫자가 커서 end_priority와 start_priority라 했지만, 이 문제를 더 쉽게 이해하기 위해선 반대로 바꾸는것도 한다.

왜냐하면 우선순위가 클수록 먼저 실행이 되기 때문이다.

그러면 우리는 시간 T를 찾는것이다.

시간 T를 찾는 방법은 다음 과 같다. 특정 priority일때까지 실행된 모든 프로세스의 개수를 세주는 것이다.

priority가 실행된 개수가 곧 실행시간이기 때문이다.

여기서 주의해야할점은 get_process(priority) == T 를 만족하는 priority가 많을 것이다.

그러므로, 우리는 priority가 현재보다 1이 커졌을때 T보다 작아지는 경우를 찾아야,

구하고자하는 실행시간 T에 실행되는 process를 찾을 수 있다.

나머지는 이분탐색처럼 하면 되는데 여기서 주의해야할점은 다음과 같다.

priority가 높을수록 일찍 실행되고, 낮을수록 늦게 실행된다.

만약 K라는 priorty까지 실행되는 priority의 개수를 구해야한다면,

K <= start_priority 와 같다면, 이 process_id가 가진 모든 실행시간을 쓴 것이기 때문에 전부 더해주면 된다.

그리고 start_priority < K <= end_priority 일때에는

end_priority - K + 1까지가 프로세스가 실행된 것이기 때문에 이 부분을 더해주면 된다.

마지막으로, 우리가 구한 get_process(mid_priority) >= T  와 get_process(mid_priority+1)<T를

만족하는 mid_priority에서 실제로 실행된 priority를 구해야한다.

get_process(mid_priority)  - get_process(mid_priority+1) 을 빼준값을 remain_priority_cnt라 하고

id 1부터 해서 mid_priorty가 해당 프로세스의 start_point와 end_point 사이에 있으면  이 값을 한개씩 줄여주면서 

0이 되었을때 실제로 실행된 process_id이므로 그때의 process_id를 출력해주면 된다.

그리고, get_process에서 특정 process에 대한 total_cnt는 동일할것이기 때문에 캐싱을 해주면 된다.

또한 dp테이블로 만든게 아닌, 함수이므로, functools의 lru_cahce를 이용하는 방법도 있다.

import heapq
import sys
input = sys.stdin.readline

T,N = map(int,input().split())

heap_list = []


for _ in range(N):
    id_num,times,C = map(int,input().split())
    heapq.heappush(heap_list,(-C,id_num,times))

result = []
for _ in range(T):

    prioty,id_num,times = heapq.heappop(heap_list)
    times -= 1
    result.append(id_num)
    if times != 0:
        heapq.heappush(heap_list,(prioty+1,id_num,times))


for i in range(T):
    sys.stdout.write(str(result[i])+'\n')

시간초과에 많이 힘들었던 문제였다. 문제를 푸는 로직은 맞지만, 출력을 하는데 시간이 오래 걸리는것 같다.

이 문제의 주어진 조건은 한 타임에 실행된 프로세스를 제외한, 나머지 프로세스들의 우선순위가 전부 1이 증가한다.

이 말의 뜻은 자기만 우선순위가 1이 줄어드는것과 같다.

그러므로 이 문제는 heapq를 이용해서 1순위로 priority가 가장 높은게 가장 앞으로 오게, 그 다음은 id가 가장 작은게 오도록 넣어준다.

그리고 하나씩 꺼내면서 시간을 줄여주고, 우선순위도 줄여주는데 max_heapq를 해야하므로, 여기서는 +1을 해주었다.

만약 시간이 0 이면 그 프로세스는 실행이 안되므로, push를 해주지 않았다.

import heapq
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
arr.sort()
# 끝나는 시간들을 저장해놓는 배열
end_time_list = []
for start_time,end_time in arr:
    if end_time_list:
        # 가장 빨리 끝나는 시간보다, 시작시간이 더 큰 경우, 회의실을 대체해서 쓸수 있다.
        if end_time_list[0] <= start_time:
            heapq.heappop(end_time_list)
        # 그리고 회의실에 새 끝나는 시간을 넣어준다.
        heapq.heappush(end_time_list,end_time)
    else:
        heapq.heappush(end_time_list,end_time)
print(len(end_time_list))

N = int(input())

metting = []
for _ in range(N):
    start,end = map(int,input().split())
    metting.append([start,1])
    metting.append([end,-1])
metting.sort()
result = 0
metting_cnt = 0 
for _,state in metting:
    metting_cnt += state
    result = max(metting_cnt,result)
print(result)