def solution(routes):
routes = sorted(routes, key=lambda x: x[1])
last_camera = -30000
answer = 0
for route in routes:
if last_camera < route[0]:
answer += 1
last_camera = route[1]
return answer
def solution(triangle):
for i in range(len(triangle) -1 ) :
triangle[i+1][0] += triangle[i][0]
triangle[i+1][-1] += triangle[i][-1]
for i in range(2, len(triangle)) :
for j in range(1, len(triangle[i]) -1) :
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
return max(triangle[-1])
def ancestor(node, parents):
if parents[node] == -1:
return node
else:
return ancestor(parents[node], parents)
def solution(n, costs):
answer = 0
costs.sort(key = lambda x : x[2])
parents = [-1]*n
bridges = 0
while bridges < n-1 :
v1, v2, cost = costs.pop(0)
if (next_v1 := ancestor(v1, parents)) != ancestor(v2, parents):
answer += cost
parents[next_v1] = v2
bridges += 1
return answer
import heapq
def solution(jobs):
n = len(jobs)
answer = 0
jobs.sort()
cur, cost = jobs.pop(0)
ready_que = [[cost, cur]]
while ready_que :
cost, arrive = heapq.heappop(ready_que)
cur += cost
while jobs and jobs[0][0] <= cur :
arrive_, cost_ = jobs.pop(0)
heapq.heappush(ready_que, [cost_, arrive_])
answer += cur - arrive
if jobs and not ready_que :
cur, cost = jobs.pop(0)
ready_que = [[cost, cur]]
return answer // n
from collections import defaultdict
def solution(n, edge):
graph = defaultdict(list)
for v1, v2 in edge :
graph[v1].append(v2)
graph[v2].append(v1)
visited = [0, 1] + [0]*(len(graph)-1) # 0๋ฒ index๋ ๋ฒ๋ฆฌ๊ณ 1๋ฒ index๋ถํฐ ๋ฐฉ๋ฌธ ํ์ธ
que = graph[1]
depth = 0
while que :
for _ in range(len(que)) :
child = que.pop(0)
if not visited[child] :
visited[child] = depth + 1
que.extend(graph[child])
depth += 1
return visited.count(depth-1)
def solution(a):
answer = 2
l_min = a[0]
r_min = a[-1]
for i in range(1, len(a)-1) :
if l_min > a[i] :
answer += 1
l_min = a[i]
if r_min > a[len(a)-1-i] :
answer += 1
r_min = a[len(a)-1-i]
return answer -1 if l_min == r_min else answer
import datetime
def solution(lines):
time_interval = []
answer = 0
for line in lines :
date, end_time, take_time = line.split(' ')
end = datetime.datetime.strptime(date+' '+end_time, '%Y-%m-%d %H:%M:%S.%f')
start = end - datetime.timedelta(seconds = float(take_time[:-1])-0.001)
time_interval.append((start.timestamp(), end.timestamp()+0.999))
time_interval.sort()
for time_ in [log for start_to_end in time_interval for log in start_to_end]:
cnt = 0
for start, end in time_interval:
if start <= time_ <= end :
cnt += 1
answer = max(answer, cnt)
return answer
๋ด์ฝ๋๋ ์๋๋ฐ ๋๋ณด๋ค ๋ ์์ง์ ๊ฐ์ ธ์ด(์๋, ๊ฐ๋ ์ฑ)
def visit(node, graph, visited):
visited[node] = 1
for child in range(len(graph[node])):
if not visited[child] and graph[node][child] == 1:
visit(child, graph, visited)
def solution(n, computers):
visited = [0] * n
answer = 0
for node in range(n):
if not visited[node]:
visit(node, computers, visited)
answer += 1
if sum(visited) == n:
break
return answer
from collections import defaultdict
from itertools import product
def solution(N, number):
if N == number : return 1
N_combinations = defaultdict(set)
calculations = ['+', '-', '*', '/']
for n in range(1, 9) :
N_combinations[n].add(int(str(N)*n))
for i in range(1, n) :
for x, sign, y in product(N_combinations[i], calculations, N_combinations[n-i]) :
if sign == '/' and y == 0 : continue
res = eval(str(x)+sign+str(y))
N_combinations[n].add(res)
if number in N_combinations[n] :
return n
return -1
from functools import reduce
def solution(n):
return reduce(lambda x, n :[x[1], x[0] + x[1]], range(n), [0, 1])[-1] % 1000000007