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

def input():
    return sys.stdin.readline().rstrip()
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        groups[X].extend(groups[Y])
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())


edge_list = []
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    if x>y:
        x,y = y,x
    edge_list.append((x,y,pay))
    total_pay += pay
K = 10**9
past_pay = 0
answer = 0
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
groups = [[k] for k in range(N+1)]
edge_list.sort(key=lambda x : x[2])
while edge_list:
    x,y,pay = edge_list.pop()
    p_x,p_y = find_parents(x),find_parents(y)
    if p_x!= p_y:
        answer = answer + len(groups[p_x])*len(groups[p_y])*(total_pay-past_pay)
        answer = answer%K
        union(x,y)
    past_pay += pay
print(answer)

구사과님의 분리집합 추천 문제에 있어서, 풀었던 문제였는데 푸는데 어려웠던 문제였다. 

이 문제는 분리집합만을 이요해 푸는 문제인데, 푸는 아이디어는 다음과 같다.

모든 간선이 연결이 끊어져 있다고 생각을 하고, 간선의 비용이 가장 많은 비용 순으로 연결을 해주는 것이다.

문제에 주어진 Cost(u,v)는 u,v가 연결이 안될때까지 최소비용의 간선을 제거해주는 것이다.

즉 역으로 생각하면  간선의 비용이 가장 많은 비용 순으로 연결을 해줄때, 처음 u,v가 같은 집합이 되면,

그 전까지 연결된 비용을 제외한 나머지 비용들이, 이 u,v의 Cost가 될 수 있다.

즉 전체 간선의 연결비용을 구한 상태에서 비용이 높은 순으로 연결을 해주면서 연결이 되었을때 까지의 누적 비용을

뺀 값이 해당 cost(u,v)인 것을 알 수 있게 된다.

그러면 여기서 고민사항은 다음과 같다.

서로 단독집합일때에는 위와 같이 한다고 할때, 만약에 서로 다른 집합에 이미 속해있는 상황에서는 어떻게 해야할지, 

일 것이다.

이 문제는 문제에서 cost(u,v)에서 u<v 이므로, 우리는 한가지 정보를 더 저장을 시켜줘야한다.

그것은 부모에 해당 집합에 속해있는 노드를 저장시켜놓는것이다.

그래서 우리는 각 부모들에 노드를 저장시켜주고, 그 노드의 수를 서로 곱해주면 두 집합에서 나올 수 있는

u,v의 집합의 개수와 동일 하다.

정리하면

(total_pay - past_pay) *len(group[parent_u]) *len(group[parent_v]) 로 나타낼수 있다.

위의 코드를 통해 AC를 받을 수 있었다. 이 문제의 아이디어를 떠오르는데 힘들었고, 구현을 하는데 어려움이 많았다.

아직 분리집합에 대해 잘 모르고, 응용하는법에 대해 잘 몰랐다는 것을 알게 되었다.

import sys

def input():
    return sys.stdin.readline().rstrip()
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        groups[X] +=groups[Y]
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())


edge_list = []
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    if x>y:
        x,y = y,x
    edge_list.append((x,y,pay))
    total_pay += pay
K = 10**9
past_pay = 0
answer = 0
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
groups = [ 1 for _ in range(N+1)]
edge_list.sort(key=lambda x : x[2])
while edge_list:
    x,y,pay = edge_list.pop()
    p_x,p_y = find_parents(x),find_parents(y)
    if p_x!= p_y:
        answer = answer + groups[p_x]*groups[p_y]*(total_pay-past_pay)
        answer = answer%K
        union(p_x,p_y)
    past_pay += pay
print(answer)

이 코드는 노드를 전부 저장하는게 아닌, 노드의 개수를 저장해주는 방식으로 바꾼 코드이다.

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 해주면 된다.

from collections import deque
def func(x):
    return x[0]
T = int(input())

for _ in range(T):
    N,M = map(int,input().split())

    arr = list(map(int,input().split()))
    queue = deque()
    for ind,val in enumerate(arr):
        queue.append((val,ind))

    cnt = 0
    while queue:
        val, ind = queue.popleft()
        if not queue or val >= max(queue,key=func)[0]:
            cnt += 1
            if ind == M:
                break
        else:
            queue.append((val,ind))

    print(cnt)

문제에 주어진대로 구현을 하면 되는 문제이다.

단 다른점은 queue에 초기에 현재의 값과 idx의 값을 동시에 넣어주고,

원하는 ind에 도착하면 멈춰주는식으로 했다.

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
from collections import deque
input = sys.stdin.readline



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

order_list = list(map(int,input().split()))

stack_list = [[[],set()] for _ in range(N+1)]
card_deck = deque()
result = []
for _ in range(T):
    input_list = list(input().split())
    card_deck.append(input_list)

num_occupy_set = set()
for ind in order_list:
    if len(stack_list[ind][0]) > 0:
        cu_card = stack_list[ind][0][0]
        result.append(cu_card[0])
        if cu_card[2] in num_occupy_set:
            continue
        else:
            stack_list[ind][0].pop(0)
            stack_list[ind][1].add(cu_card[2])
            num_occupy_set.add(cu_card[2])

    else:
        cu_card = card_deck.popleft()
        result.append(cu_card[0])

        if cu_card[1] == 'next':
            continue
        elif cu_card[1] == 'acquire':
            if cu_card[2] in num_occupy_set:
                stack_list[ind][0].append(cu_card)
            else:
                stack_list[ind][1].add(cu_card[2])
                num_occupy_set.add(cu_card[2])
        else:
            stack_list[ind][1].remove(cu_card[2])
            num_occupy_set.remove(cu_card[2])

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

문제에 주어진대로 사람 수대로, deck을 만들어준뒤, 순서대로 명령어를 실행해주면 되는 구현 문제였다.

만약에 acquire 카드를 썼지만, 카드더미에 없으면, 자기 덱에 카드를 넣어주고, 그 카드를 다시 실행해주는 구현부분만 제대로 해주면 된다.

 이 코드는 깔끔하지 못해서 대회가 끝나고 난뒤에 고친 코드는 밑에 있다.

import sys
from collections import deque
input = sys.stdin.readline
N,T = map(int,input().split())

turns = list(map(int,input().split()))



card_deck = deque()

for _ in range(T):
    temp = input().rstrip().split(' ')
    card_deck.append(temp)

occupy_card = [[] for _ in range(N+2)]
result = []
used_card_num = set()
for i in range(T):
    person = turns[i]

    if len(occupy_card[person])>0:
        card_num,wanted_num = occupy_card[person]
        result.append(card_num)
        if wanted_num in used_card_num:
            continue
        else:
            used_card_num.add(wanted_num)
            occupy_card[person] = []
    else:
        card_num,*rests= card_deck.popleft()
        result.append(card_num)
        if rests[0] == 'next':
            continue
        elif rests[0] == 'acquire':
            if rests[1] in used_card_num:
                occupy_card[person] = (card_num,rests[1])
            else:
                used_card_num.add(rests[1])
        elif rests[0] == 'release':
            used_card_num.remove(rests[1])


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

어차피 보유하고 있을수 있는 카드는 한장이므로,  set을 굳이 넣을 필요가 없고, used_card를 통해, 쓴 카드와 안쓴 카드를 구분을 해줬다.