Coding 공부

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의 길이로 답을 출력해주었다.

print(''.join(sorted(input())[::-1]))

정렬을 해준뒤 역으로 출력해준다.

import sys

T = int(input())

for tc in range(T):
    N = int(input())
    result = 0
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()
    min_value = arr[0][1]
    for ind in range(N):
        if ind == 0:
            result += 1
        else:
            if min_value > arr[ind][1]:
                min_value = arr[ind][1]
                result += 1
    print(result)

처음에 입력 받은 그 상태로 서류점수 자체로 sort를 해줬다. 그러면  1번 지원자를 제외한 나머지 지원자들은 이미 서류점수에서, 자기보다 잘 본 사람이 있는 것이다. 

그렇기 때문에 면접점수에서 앞의 사람보다. 순위가 높으면, 두 분야에서 자기보다 잘 본 사람이 있는 것이기 때문에, 최종 탈락하는 것이다.

그래서, 제일 첫번째 지원자의 면접점수를 최소값으로 해주고, 이 값보다 좋은 순위가 있으면 교체를 해주면서 최종합격자 수를 늘려주면 된다.

하지만 이렇게 할시 무조건 처음에 sort를 해야하기 때문에 5000ms 이상의 시간이 걸린다.

import sys

T = int(input())

for tc in range(T):
    N = int(input())
    result = 1
    arr = [0]*(N+1)
    for _ in range(N):
        x,y = map(int,sys.stdin.readline().split())
        arr[x] = y
    min_value = arr[1]
    for ind in range(2,N+1):
        if min_value > arr[ind]:
            min_value = arr[ind]
            result += 1
    print(result)

개선한 방안은 어차피 중복되는 수는 없고 1~N 까지의 순위는 무조건 있기 때문에, 길이가 (N+1)인 1차원 리스트를 만들어주고, index가 서류점수 value가 면접점수가 되도록 한다.

그리고 그 다음은 위와 똑같이 진행해주면 된다.

sort를 진행하지 않기 때문에 실행시간이 확연히 줄어드게 된다.

# 출력을 할때에도 여러번 반복하는 것이면 곱해서 하자 곱하기가 된다.


import sys
N = int(sys.stdin.readline())
array = [0 for _ in range(10001)]
for _ in range(N):
    num = int(sys.stdin.readline())
    array[num] += 1
for k in range(10001):
    print(f'{k}\n'*array[k],end='')

처음에 출력을 할떄

if array[k]:
   for _ in range(array[k]):
        pirnt(k)

위와 같은 식으로 했었다. 그랬더니 무수한 메모리 초과 오류가 발생했다.

아마도 매번 range(array[k]) 만큼의 리스트를 만들어줘야했기에, 메모리가 초과 된것 같다.

크게 두가지 방법이 있는것 같아다.

sys에 있는 write를 이용해 출력을 하는방법과

print()를 횟수만큼 곱해서 하는방법이 있었다.

그 중에서 나는 후자를 선택했다.

import sys

N = int(sys.stdin.readline())
array = [0]* 2000001
for _ in range(N):
    num = int(sys.stdin.readline())
    num += 1000000
    array[num] += 1

for num in range(2000001):
    print(f'{num-1000000}\n'*array[num],end='')

문제에서 수의 크기가 100만이므로 200만1개의 리스트를 만들어주고 반복문을 돌려주었다.