Coding 공부

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)

import sys
import heapq

input = sys.stdin.readline


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

visited = [False]*K
jewel = []
for _ in range(N):
    m,v = map(int,input().split())
    heapq.heappush(jewel,(m,v))

bags = []
for _ in range(K):
    bags.append(int(input()))

bags.sort()
result = 0
possible_jewel = []
for bag in bags:
    while jewel and jewel[0][0] <= bag:
        m,v = heapq.heappop(jewel)
        heapq.heappush(possible_jewel,-v)
    
    if possible_jewel:
        result -= heapq.heappop(possible_jewel)
        
    

print(result)

import heapq
import sys
N = int(input())


max_heapq = []
min_heapq = []
for _ in range(N):
    number = int(sys.stdin.readline())
    if len(max_heapq) == len(min_heapq):
        heapq.heappush(max_heapq,-number)
    else:
        heapq.heappush(min_heapq,number)
    if min_heapq and max_heapq and min_heapq[0] < -max_heapq[0]:
        max_number = -heapq.heappop(max_heapq)
        min_number = heapq.heappop(min_heapq)

        heapq.heappush(max_heapq,-min_number)
        heapq.heappush(min_heapq,max_number)
    print(-max_heapq[0])

우선순위 힙을 사용하는 기본적인 문제인 것 같다.

과거에도 다익스트라 알고리즘 문제를 풀때 우선순위힙큐를 사용했지만, 여전히 우선순위 힙을 사용하는데, 어려움을 겪었던 문제다.

문제 자체의 기본적인 생각은 다음과 같다. 

가운데 값을 기준으로 가운데 값보다 큰 경우는 무조건 우측에 두는 것이다.  그리고 작은 값은 좌측에 두는 것이다.

그러므로, min_heapq는 가운데 값을 기준으로 우측에 있는 값이고, max_heapq는 가운데 값을 기준으로 좌측에 있는 값이다.

문제 조건 중 가운데 값을 출력하고, 짝수일경우 가운데 값 2개 중 작은 값을 출력을 해야한다. 그러므로, max_heapq가 min_heapq보다 크기가 커야한다. 그래서 max_heapq와 min_heapq가 같은 크기이면, max_heapq에 먼저 넣어주고, 아닐 경우 min_heapq를 넣어줘야한다.

그리고 heapq는 무조건 최소값을 pop해주는 특징이 있으므로, max_heapq를 저장할때에는 가장 큰 값이 가장 먼저 나올수 있도록 -를 곱해줘야한다.

순서에 따라 맞춰서 max_heapq와 min_heapq에 순차적으로 넣어줘야한다. 하지만, 들어오는 입력값에 따라 가끔씩 min_heapq의 첫번째값이 max_heapq의 첫번째값보다 작은 경우가 생길수가 있다. 그럴 경우 두개를 바꿔주는 과정이 필요하다.

무조건 max_heapq의 첫번째 값이 전체의 가운데값이 되기위한 조치이다.

그리고 난뒤에, max_heapq의 첫번째 값을 출력해주면 된다.

heapq라는 라이브러리를 사용하면, 그리 어렵지 않은 문제이다. 하지만 나는 아직 트리와 우선순위힙에 대해서 잘 모르므로, 나중에 트리와 우선순위힙에 대해 더 자세히 공부하고, 라이브러리가 아닌 직접 구현으로 풀 수 있도록 연습해야겠다. 

import collections

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

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    n1,n2,d = map(int,input().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node = start

while True:
    visited[node] = False
    for ind,dis in graph[node]:
        distance[ind] = min(distance[ind],distance[node]+dis)
    next_node = -1
    next_min_distance = INF
    for ind in range(N+1):
        if visited[ind] and next_min_distance > distance[ind]:
            next_min_distance = distance[ind]
            next_node = ind
    if next_node != -1:
        node = next_node
    else:
        break

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

평소에 하던 다익스트라 문제였고, 평상시 하던대로 로직을 짜서 실행시켰다 하지만 시간초과라는 결과가 나왔다.

평소에 heapq라는 라이브러리가 익숙치 않아서 쓰지 않았던 heapq를 썼다. heapq를 써서 문제를 풀었다.

import heapq
import sys
N,M = map(int,input().split())
start = int(input())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    n1,n2,d = map(int,sys.stdin.readline().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

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

while node_list:
    current_distance,node= heapq.heappop(node_list)
    visited[node] = True
    if distance[node]<current_distance:
        continue
    for next_node,next_dis in graph[node]:
        if visited[next_node]:
            temp_distance = current_distance + next_dis
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(distance[next_node],next_node))

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

heapq를 썼을시에는 통과가 가능했다.

시간복잡도는 heapq가 더 빠르니, heapq에 대해서도 공부해야겠다.