Coding 공부

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
 
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    temp = list(map(int,input().split()))
    for number in temp:
        heapq.heappush(arr,number)
    while len(arr) > N:
        heapq.heappop(arr)
 
 
 
result = heapq.heappop(arr)
print(result)

문제의 조건 중 N이 1500이라서 전부 arr에 저장을 하면 메모리가 부족할 가능성이 있다.

그래서 arr의 크기를 N으로 고정시켜놓고 그보다 클시에는 pop을 해주는 방식으로 했다.

import heapq
import sys
 
input = sys.stdin.readline
 
N = int(input())
arr = []
 
for i in range(N):
    input_list = map(int,input().split())
    if i == 0 :
        for number in input_list:
            heapq.heappush(arr,number)
    else:
        for number in input_list:
            if number > arr[0]:
                heapq.heappushpop(arr,number)
big_list = heapq.nlargest(N,arr)
print(big_list[N-1])

 두번째 방식은 heapq의 기능을 좀 더 잘 쓰는것이다.

heappushpop을 하면 heapop을 하고 heappush를 하는 것보다 더 빠르다.

이걸 이용해서 위와 같이 똑같이 해주고,

마지막에는 전체 arr 중에서 N개의 큰 수 만을 뽑아내는 methods를 활용해준다.

# stkang9409 풀이 해석
 
def find_max_value(x):
    return arr[max_row_list[x]][x]
 
import sys
 
input = sys.stdin.readline
 
 
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
 
max_row_list = [N-1]*N
# 각 열마다 가장 큰 값은 N-1번 행에 있는 값이다.
# 매번 돌면서 각 열마다 가장 큰값들을 비교해, 가장 큰 값이 있는 열의 index 값을 하나씩 줄여나간다.
# 그렇게 하면 마지막 N번째에 가장 큰 값을 가지는 열의 값이 N번째로 큰 수의 열값이 되고
# 그 때 저장된 위치의 값이 행이된다.
for cnt in range(N):
    max_col_index = 0
    for col in range(N):
        max_col_index = max(col,max_col_index,key= find_max_value)
    if cnt == N-1:
        print(arr[max_row_list[max_col_index]][max_col_index])
    max_row_list[max_col_index] -= 1

다른 분의 풀이를 해석한 것으로, 문제의 조건을 활용해서 하는 방식이다.

각 열의 값은 다음 행의 값보다는 작다는 점을 이용해,

N번을 반복하면서 가장 큰 값들이 위치한 col의 row값을 하나씩 줄여주는 방식이다.

import heapq
import sys
 
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    temp = list(map(int,input().split()))
    for number in temp:
        heapq.heappush(arr,number)
    while len(arr) > N:
        heapq.heappop(arr)
 
 
 
result = heapq.heappop(arr)
print(result)

N번째 큰수를 구하는 거였고, N의 최대값이 1500이므로, 전체 input을 받아서 행렬을 만드는게 아닌, 

한 행이 들어올때마다 판별을 해줘야한다고, 생각했다.

그리고 우리가 구하고 싶은 것은 N번째 이므로, 저장할 칸은 N 칸만 있으면 된다고 생각했고, 이걸 heapq를 이용해서 구현했다.

처음 구현한 방식은 일단 한 행을 전부 집어넣고, 리스트의 길이가 N이 될때까지 heappop을 계속 해주었다. 

그리고 마지막으로 heappop을 해서 원하는 결과를 얻었다.

import heapq
import sys
 
input = sys.stdin.readline
 
N = int(input())
arr = []
 
for i in range(N):
    input_list = map(int,input().split())
    if i == 0 :
        for number in input_list:
            heapq.heappush(arr,number)
    else:
        for number in input_list:
            if number > arr[0]:
                heapq.heappushpop(arr,number)
big_list = heapq.nlargest(N,arr)
print(big_list[N-1])

두번째 방법은 heapq 모듈을 좀 더 활용하는 방법이다.  무조건 넣고 길이 N이 될때까지 계속 pop 하는 것이 아닌.

heappushpop을 쓰는 것이다. 이것은 heap에 먼저 push를 한뒤에 가장 작은 값을 pop 하는 것으로,

heappush와 heappop을 쓰는 것보다 실행속도가 더 빠르다.

그리고 마지막으로 heapq.nlargest를 쓰는 것이다. 이 메소드는 정의된 요소에서 가장 큰 순서대로 n개로 구성된 리스트를 반환해주는 메소드이다. 이걸 이용하면, 정렬을 한 효과와 동일하다.

# stkang9409 풀이 해석
 
def find_max_value(x):
    return arr[max_row_list[x]][x]
 
import sys
 
input = sys.stdin.readline
 
 
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
 
max_row_list = [N-1]*N
# 각 열마다 가장 큰 값은 N-1번 행에 있는 값이다.
# 매번 돌면서 각 열마다 가장 큰값들을 비교해, 가장 큰 값이 있는 열의 index 값을 하나씩 줄여나간다.
# 그렇게 하면 마지막 N번째에 가장 큰 값을 가지는 열의 값이 N번째로 큰 수의 열값이 되고
# 그 때 저장된 위치의 값이 행이된다.
for cnt in range(N):
    max_col_index = 0
    for col in range(N):
        max_col_index = max(col,max_col_index,key= find_max_value)
    if cnt == N-1:
        print(arr[max_row_list[max_col_index]][max_col_index])
    max_row_list[max_col_index] -= 1

마지막 풀이는 stkang9409님 코드를 보고 분석하것이다.

이 방법은 heapq를 쓴 것이 아닌, 문제의 조건을 보고 푼 방식이다.

위의 heapq를 쓴다면 신경 안 쓸 조건이지만, 문제에 주어진 조건을 보면

각 열의 값들은 그 다음행의 값보다 작다는 것이다. 즉 A열의 B행의 값은 B+1행보다는 무조건 작다는 것이다.

이 점을 이용해 N번째로 큰 값을 알 수 있다.

만약 조건 N이 주어진다면

각 열마다 가장 큰 행의 위치는 N-1일것이다. (0행부터 시작한다)

이걸 하나의 리스트로 구성하면

max_row_list = [N-1, N-1,.... N-1]

일것이고, 이 리스트의 인덱스는 arr의 열의 값이 될것이고, 해당 index의 값은 행이 될것이다.

각 열에서의 최대값을 비교해서 가장 큰 값을 구해준다.

각 열의 최대값은 arr[ max_row_list[ind] ] [ ind ] 가 될 것이다.

이렇게 하면 가장 큰 값이 있는 열의 값을 구할 수 있다. 그 열의 값이 있는 max_row_list의 값을 1을 낮춰준다.

이런 식으로 반복 하면 N번 반복하면 N번째로 큰 수를 알 수 있다.

예시 ) 

12 7 9 15 5

13 8 11 19 6

21 10 26 31 16

48 14 28 35 25

52 20 32 41 49

위와 같이 주어지면 

max_row_index = [4,4,4,4,4] 가 될 것이다.

--  1번째  --

arr[4][0],arr[4][1],arr[4][2],arr[4][3],arr[4][4] 의 값을 비교해보면 arr[0][4]가 가장 작다.

그러면 max_row_index 의  0번 인덱스의 값을 1 줄여준다,

max_row_index = [3,4,4,4,4] 가 된다.

-- 2번째 --

arr[3][0],arr[4][1],arr[4][2],arr[4][3]arr[4][4] 의 값을 비교해보면 arr[4][4]의 49가 가장 크다.

그러면 4번 인덱스이고 해당 max_row_index의 값을 줄여준다.

max_row_index = [3,4,4,4,3]

-- 3번째 --

arr[3][0],arr[4][1],arr[4][2],arr[4][3]arr[3][4] 의 값을 비교해보면 arr[3][0]의 48이 가장 크다.

그러면 0번 인덱스이고 해당 max_row_index의 값을 줄여준다.

max_row_index = [2,4,4,4,3]

-- 4번째 --

arr[2][0],arr[4][1],arr[4][2],arr[4][3]arr[3][4] 의 값을 비교 해보면  arr[4][3]의 41이 가장 크다.

그러면 3번 인덱스이고 해당 max_row_index의 값을 줄여준다.

max_row_index = [2,4,4,3,3] 

--5번째 (마지막) --

arr[2][0],arr[4][1],arr[4][2],arr[3][3],arr[3][4] 의 값을 비교 해보면 arr[3][3]의 35이 가장 크다

그리고 우리가 구하던 N번째로 큰 값이므로 이 값을 그대로 출력해주면 된다.

설명이 많이 부족하겠지만, 최대한 자세히 설명을 했다.

마지막 풀이는 문제의 조건을 활용해 각 열을 기준으로 하는 최대 행을 저장해주는 리스트를 만들어두고

각 열의 최대값을 갱신해주면서 하는 방식으로 보면 된다. 

import heapq
import sys
input = sys.stdin.readline
N = int(input())
 
times = []
for _ in range(N):
    input_tuple = tuple(map(int,input().split()))
    heapq.heappush(times,input_tuple)
 
end_time_list = []
answer = 0
while times:
    start_time,end_time = heapq.heappop(times)
    if not end_time_list:
        answer += 1
        heapq.heappush(end_time_list,end_time)
    else:
        if end_time_list[0] > start_time:
            heapq.heappush(end_time_list,end_time)
            answer += 1
        else:
            heapq.heappop(end_time_list)
            heapq.heappush(end_time_list,end_time)
            
        
print(answer)

우선순위 힙을 응용한 문제이다. 먼저 (시작시간,종료시간)이 입력을 들어왔을때, 하나의 리스트에 저장을 해준다.

그리고 그것을 시작시간을 기준으로 정렬을 해준다.

그리고 하나씩 꺼내면서 판단을 해주면 된다.

end_time_list가 비워져있으면, 종료시간을 그냥 넣어준다.

end_time_list의 첫번째 값 즉. 가장 먼저 강의가 종료되는 시간보다, 현재 강의의 시작시간이 더 빠르면(작으면) 강의실을 여러개 구해야한다.

그러므로 answer를 +1 해주고, end_time_list에 현재 강의의 종료시간을 넣어준다.

그렇지 않을시에는, 강의실을 추가로 빌린필요가 없으므로, 가장 첫번째 값을 없애고, 현재 강의 종료시간을 end_time_list에 저장을 시켜준다.

end_time_list의 가장 첫번째 값은 가장 작은 값으로 유지되어야하므로, 우선순위 큐인 heapq를 사용했다.

import heapq
import sys
input = sys.stdin.readline
 
N = int(input())
class_list = []
for _ in range(N):
    start_time,end_time = map(int,input().split())
    class_list.append((start_time,end_time))
 
class_list.sort()
end_time_list = []
for start_time,end_time in class_list:
    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))
 

좀 더 깔끔한 방식으로 푼 코드이다. 강의의 전체 정보를 저장하는 리스트는 굳이, 우선순위 힙을 쓸필요가 없으므로, 일반리스트로 쓰면서 정렬을 해줬다.

그리고 다른 변수로 answer를 저장하던걸 어차피, end_time_list의 길이와 답이 일치하므로, end_time_list의 길이로 답을 출력해주었다.

from collections import deque
import bisect
import sys
input = sys.stdin.readline
T = int(input())
 
for _ in range(T):
    stack = deque()
    stack_dict = dict()
    for _ in range(int(input())):
        command,val = input().split()
        val = int(val)
        if command == 'I':
            if stack_dict.get(val):
                stack_dict[val] += 1
            else:
                bisect.insort_left(stack,val)
                stack_dict[val] = 1
        else:
            if val == 1:
                if stack:
                    last_number = stack[-1]
                    if stack_dict[last_number] == 1:
                        stack_dict.pop(last_number)
                        stack.pop()
                    else: 
                        stack_dict[last_number] -= 1
            else:
                if stack:
                    first_number = stack[0]
                    if stack_dict[first_number] == 1:
                        stack_dict.pop(first_number)
                        stack.popleft()
                    else:
                        stack_dict[first_number] -= 1
    if stack:
        print(stack[-1],stack[0])
    else:
        print('EMPTY')

정렬된 행렬일때 쓸 수 있는 bisect 라이브러리를 이용해서, 이진탐색 후, deque에 넣어주었다.

뺄때 매번 insert, pop을 하면 연산시간이 오래걸리므로, dictionary로 개수를 세주었고, dictionary가 0이 될때 pop을 해주었다.