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
def check(node):

    path_set = set()
    stack = [(node,distance[node])]

    while stack:
        node,dis = stack.pop()
        for prev_node in graph[node]:
            if (prev_node,node) not in path_set:
                if distance[prev_node] + graph[prev_node][node] == dis:
                    path_set.add((prev_node,node))
                    stack.append((prev_node,distance[prev_node]))
    if (G,H) in path_set or (H,G) in path_set:
        return True
    return False



def dijkstra(node):
    distance[node] = 0
    node_list = []
    heapq.heappush(node_list,(0,node))
    while node_list:
        cur_dis, cur_node = heapq.heappop(node_list)
        if distance[cur_node] > cur_dis:
            continue
        for next_node in graph[cur_node]:
            if distance[next_node] > graph[cur_node][next_node] + cur_dis:
                distance[next_node] = graph[cur_node][next_node] + cur_dis
                heapq.heappush(node_list,(graph[cur_node][next_node] + cur_dis,next_node))

    


input = sys.stdin.readline

for _ in range(int(input())):
    N,M,T = map(int,input().split())
    graph = [{} for _ in range(N+1)]
    start,G,H = map(int,input().split())
    for _ in range(M):
        x,y,pay = map(int,input().split())
        graph[x][y] = pay
        graph[y][x] = pay
    
    candidate_list = [int(input().rstrip()) for _ in range(T)]
    INF = float('inf')
    distance = [INF]*(N+1)
    dijkstra(start)
    result = []
    for check_node in candidate_list:
        if check(check_node):
            result.append(check_node)

    result.sort()
    print(*result)

import sys

input = sys.stdin.readline

def combination(ind,len_string,combi):
    if ind == len_string:
        print(combi)
    else:
        for k in range(len_string):
            if visited[k]:
                temp = combi+string_list[k]
                if temp not in record:
                    visited[k] = False
                    record.add(temp)
                    combination(ind+1,len_string,temp)
                    visited[k] = True 



N = int(input())

for _ in range(N):
    string_list = list(input().strip())
    string_list.sort()
    len_string = len(string_list)
    visited = [True]*(len(string_list))
    record = set()
    combination(0,len_string,'')

from collections import deque
def find_passenger(start,K):
    stack = deque()
    stack.append((*start,K))
    visited = [[True]*N for _ in range(N)]
    visited[start[0]][start[1]] = False
    if passenger_arr[start[0]][start[1]] < 0:
        result = [start[0],start[1],K,passenger_arr[start[0]][start[1]]]
        passenger_arr[start[0]][start[1]] = 0
        return result

    candidate = []
    while stack:
        x,y,fuel = stack.popleft()
        if fuel < 0:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if passenger_arr[nx][ny] < 0:
                        candidate.append([nx,ny,fuel-1,passenger_arr[nx][ny]])
    if candidate:
        candidate.sort(key=lambda x : (-x[2],x[0],x[1]))
        result = candidate[0]
        passenger_arr[result[0]][result[1]] = 0
        return result
    else:
        return False

def find_destination(passenger):
    stack = deque()
    stack.append((passenger[0],passenger[1],passenger[2]))
    destination = destination_dict[passenger[-1]]
    visited = [[True]*N for _ in range(N)]
    visited[passenger[0]][passenger[1]] = False
    init_fuel = passenger[2]
    while stack:
        x,y,fuel = stack.popleft()
        if fuel <= 0:
            return False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if (nx,ny) == destination:
                        fuel = 2*init_fuel - fuel + 1
                        result = [nx,ny,fuel]
                        return result

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

passenger_arr = [list(map(int,input().split())) for _ in range(N)]
destination_dict = {}
taxi = list(map(lambda x : x-1 ,map(int,input().split())))
ind = 2



dx = [-1,0,1,0]
dy = [0,-1,0,1]

for _ in range(M):
    start_x,start_y,end_x,end_y = map(lambda x : x-1 ,map(int,input().split()))
    passenger_arr[start_x][start_y] = -ind
    destination_dict[-ind] = (end_x,end_y)
    ind += 1


answer = 0
cnt = 0
while cnt <M:
    passenger = find_passenger(taxi,K)
    if not passenger:
        answer = -1
        break
    destination = find_destination(passenger)
    if not destination:
        answer = -1
        break
    taxi = [destination[0],destination[1]]
    K = destination[-1]
    if K < 0:
        answer = -1
        break
    cnt += 1


if answer == -1:
    print(answer)
else:
    print(K)

경로 중간에 fuel이 0이 되어도 false 반환 안되게 함

N,M,K = map(int,input().split())
# N 은 격자
# M 은 상어의 수
# K 은 이동횟수

sharks = {}
arr = []
smell = {}
for x in range(N):
    input_list = list(map(int,input().split()))
    for y in range(N):
        if input_list[y]:
           sharks[input_list[y]] = (x,y)
           smell[(x,y)] = [K,input_list[y]]
    arr.append(input_list)
# 0 위 1 아래 2 왼쪽 3 오른쪽

shark_input_move = list(map(int,input().split()))
ind = 1
for shark_init_move in shark_input_move:
    sharks[ind] = (*sharks[ind],shark_init_move-1)
    ind += 1

shark_move = [[],]

for _ in range(M):
    temp = []
    for x in range(4):
        move_input = list(map(lambda x : x-1,map(int,input().split())))
        temp.append(move_input)
    shark_move.append(temp)



time = 0


dx = [-1,1,0,0]
dy = [0,0,-1,1]
while time <= 1000:
    move_shark = {}
    new_smell = {}
    for shark_num in sorted(sharks.keys()):
        x,y,dire = sharks[shark_num]
        shark_move_direction = []
        for i in shark_move[shark_num][dire]:
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <N and 0<=ny <N:
                if not smell.get((nx,ny)):
                    shark_move_direction = (nx,ny,i)
                    break
        else:
            new_dire_list = shark_move[shark_num][dire]
            for new_dire in new_dire_list:
                nx = x + dx[new_dire]
                ny = y + dy[new_dire]
                if 0<=nx<N and 0<=ny<N:
                    if smell[(nx,ny)][1] == shark_num:
                        shark_move_direction = (nx,ny,new_dire)
                        break
        if not new_smell.get((nx,ny)):
            new_smell[(nx,ny)] = [K,shark_num]
            move_shark[shark_num] = shark_move_direction
    for position in smell.keys():
        if not new_smell.get(position):
            if smell[position][0]-1>0:
                new_smell[position] = [smell[position][0]-1,smell[position][1]]
    time += 1
    print(move_shark)
    print(new_smell)
    if time == 14:
        break
    if len(move_shark.keys()) == 1:
        break
    sharks = {}
    for shark_num in move_shark.keys():
        sharks[shark_num] = move_shark[shark_num] 
    smell = {position : new_smell[position] for position in new_smell.keys()}


print(-1 if time == 1001 else time)

N,M,K = map(int,input().split())
# N 은 격자
# M 은 상어의 수
# K 은 이동횟수

sharks = {}
arr = []
smell = {}
for x in range(N):
    input_list = list(map(int,input().split()))
    for y in range(N):
        if input_list[y]:
           sharks[input_list[y]] = (x,y)
           smell[(x,y)] = [K,input_list[y]]
    arr.append(input_list)
# 0 위 1 아래 2 왼쪽 3 오른쪽

shark_input_move = list(map(int,input().split()))
ind = 1
for shark_init_move in shark_input_move:
    sharks[ind] = (*sharks[ind],shark_init_move-1)
    ind += 1

shark_move = [[],]

for _ in range(M):
    temp = []
    for x in range(4):
        move_input = list(map(lambda x : x-1,map(int,input().split())))
        temp.append(move_input)
    shark_move.append(temp)



time = 0


dx = [-1,1,0,0]
dy = [0,0,-1,1]
while time <= 1000:
    move_shark = {}
    new_smell = {}
    for shark_num in sorted(sharks.keys()):
        x,y,dire = sharks[shark_num]
        shark_move_direction = []
        my_shark_move_direction = []
        my_smell_move = True
        for i in shark_move[shark_num][dire]:
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <N and 0<=ny <N:
                if not smell.get((nx,ny)):
                    shark_move_direction = (nx,ny,i)
                    break
                elif my_smell_move and smell[(nx,ny)][1] == shark_num:
                    my_smell_move = False
                    my_shark_move_direction = (nx,ny,i) 
        else:
            shark_move_direction = my_shark_move_direction[:]
        
        if not new_smell.get((shark_move_direction[0],shark_move_direction[1])):
            new_smell[(shark_move_direction[0],shark_move_direction[1])] = [K,shark_num]
            move_shark[shark_num] = shark_move_direction
    for position in smell.keys():
        if not new_smell.get(position):
            if smell[position][0]-1>0:
                new_smell[position] = [smell[position][0]-1,smell[position][1]]
    time += 1
    if len(move_shark.keys()) == 1:
        break
    sharks = {}
    for shark_num in move_shark.keys():
        sharks[shark_num] = move_shark[shark_num] 
    smell = {position : new_smell[position] for position in new_smell.keys()}


print(-1 if time == 1001 else time)

import copy
def find_position(pools,num):
    for x in range(4):
        for y in range(4):
            if pools[x][y][0] == num:
                return (x,y)
    return False
def move_fish(pools,shark_x,shark_y):
    for fish_num in range(1,17):
        position = find_position(pools,fish_num)
        if position:
            x,y = position
            fish_dire = pools[x][y][1]

            for _ in range(8):
                nx = x + dx[fish_dire]
                ny = y + dy[fish_dire]
                if 0<=nx<4 and 0<=ny<4:
                    if not (nx == shark_x and ny == shark_y):
                        pools[x][y][0],pools[nx][ny][0] = pools[nx][ny][0],pools[x][y][0]
                        pools[x][y][1],pools[nx][ny][1] = pools[nx][ny][1],fish_dire
                        break
                fish_dire = (fish_dire+1)%8


def eating(x,y,pools):
    temp = []
    shark_dire = pools[x][y][1]
    for _ in range(3):
        nx = x + dx[shark_dire]
        ny = y + dy[shark_dire]
        if 0<=nx<4 and 0<=ny<4 and pools[nx][ny][0]>0:
            temp.append((nx,ny))
        x,y = nx,ny
    return temp


def solution(pools,shark_x,shark_y,cnt):
    global answer
    pools2 = [[col[:] for col in row]      for row in pools]
    eat_fish_size = pools2[shark_x][shark_y][0]
    pools2[shark_x][shark_y][0] = -1
    move_fish(pools2,shark_x,shark_y)
    find_fish = eating(shark_x,shark_y,pools2)
    answer = max(answer,eat_fish_size+cnt)

    for x,y in find_fish:
        solution(pools2,x,y,cnt+eat_fish_size)
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

pools = []
for x in range(4):
    arr = list(map(int,input().split()))
    temp = []
    for y in range(4):
        fish_number,dire = arr[2*y],arr[2*y+1]
        temp.append([fish_number,dire-1])
    pools.append(temp)
answer = 0

solution(pools,0,0,0)
print(answer)

def find_K(k,n,reversal):
    if n == 0:
        return reversal%2
    else:
        if k >= 2**(n-1):
            return find_K(abs(2**(n-1)-k),n-1,reversal+1)
        else:
            return find_K(k,n-1,reversal)

k = int(input())
k = k-1
print(find_K(k,60,0))

import sys

input = sys.stdin.readline

def move(target):
    x,y,dire = chess[target]

    nx = x + dx[dire]
    ny = y + dy[dire]

    if not(0<=nx<N) or not(0<=ny<N) or arr[nx][ny] == 2:
        dire = reverse_dire[dire]
        chess[target] = [x,y,dire]
        nx = x + dx[dire]
        ny = y + dy[dire]
        if not(0<=nx<N) or not(0<=ny<N) or arr[nx][ny] == 2:
            return 0

    slice_idx = 0
    for ind,horse in enumerate(chess_map[x][y]):
        if horse == target:
            slice_idx = ind
            break

    move_items = chess_map[x][y][slice_idx:]
    chess_map[x][y] = chess_map[x][y][:slice_idx]

    if arr[nx][ny]:
        move_items.reverse()

    chess_map[nx][ny].extend(move_items)

    for ind in move_items:
        chess[ind] = [nx,ny,chess[ind][2]]
    
    return len(chess_map[nx][ny]) 



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

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

chess = [[] for _ in range(M)]
chess_map = [[[] for _ in range(N)] for _ in range(N)]

chess_input = [list(map(lambda x : x-1,map(int,input().split()))) for _ in range(M)]


dx = [0,0,-1,1]
dy = [1,-1,0,0]
reverse_dire = [1,0,3,2]


for ind,info in enumerate(chess_input):
    x,y,dire = info
    chess[ind] = [x,y,dire]
    chess_map[x][y].append(ind)


cnt = 0
break_flag = False
while cnt <= 1000:
    cnt += 1

    for k in range(M):
        stack_size = move(k)
        if stack_size >= 4:
            break_flag = True
            break
    if break_flag:
        break

print(-1 if cnt > 1000 else cnt)