import sys
sys.setrecursionlimit(10**6)
class Tree:
def __init__(self,dataList):
self.data = max(dataList, key = lambda x :x[1]) # dataList 중 y값이 가장 큰 노드
leftList = list(filter(lambda x :x[0] < self.data[0] , dataList)) # data를 기준으로 왼쪽 트리
rightList = list(filter(lambda x :x[0] > self.data[0] , dataList)) # data를 기준으로 오른쪽 트리
self.left= Tree(leftList) if leftList else None # 왼쪽 트리 재귀
self.right=Tree(rightList) if rightList else None # 오른쪽 트리 재귀
def order(node,postList = [],preList = []):
postList.append(node.data[-1]+1) # postorder index
if node.left is not None:
order(node.left,postList,preList)
if node.right is not None:
order(node.right,postList,preList)
preList.append(node.data[-1]+1) # preorder index
return [postList, preList]
def solution(nodeinfo):
root = Tree([x+[i] for i, x in enumerate(nodeinfo)])
return order(root)
from itertools import product
def solution(N, road, K):
DP = [[500000] * N for _ in range(N)]
road.sort(key = lambda x : x[2], reverse = True)
for v1, v2, cost in road:
DP[v1 - 1][v2 - 1] = DP[v2 - 1][v1 - 1] = cost
for t in range(N):
DP[t][t] = 0
for via, i, j in product(range(N), repeat=3):
if DP[i][j] > (l := DP[i][via] + DP[via][j]):
DP[i][j] = l
return len([x for x in DP[0] if x <= K])
import sys
sys.setrecursionlimit(10**6)
import math
def solution(n, stations, w, begin = 1):
if not stations :
return math.ceil((n-begin+1) / (2*w+1))
station = stations.pop()
if station+w >= n :
return solution(station-w-1, stations, w, begin)
if station-w <= begin :
return solution(n, stations, w, station+w+1)
return solution(station-w-1, stations, w, begin) + solution(n, stations, w, station+w+1)
def queens(n, board, h) :
ans = 0
if h == n :
return 1
for w in range(1, n+1) :
board[h + 1] = w
if promising(board, h+1) :
ans += queens(n, board, h+1)
return ans
def promising(board, h) :
for h_ in range(1, h) :
if (w_ := board[h_]) == (w := board[h]) or h - h_ == abs(w_ - w) :
return False
return True
solution = lambda n : queens(n, [0]*(n+1), 0)
def solution(n, first = 1, second = 2, third = 3):
return solution(n-1, first, third, second) + [[first, third]] + solution(n-1, second, first, third) if n else []
def solution(n, s):
num, res = divmod(s, n)
if n > s :
return [-1]
answer = [num for _ in range(n)]
for i in range(res) :
answer[-1-i] += 1
return answer
입국심사와 매우 비슷한 문제다. 혹시 이문제를 모른다면 무조건 보고와야한다.
def check(stones, k, people) :
sinked = 0
for stone in stones :
sinked = sinked + 1 if stone < people else 0
if sinked == k : return False
return True
def solution(stones, k):
min_ = min(stones)
max_ = max(stones)
if min_ == max_ : return min_
while min_ < max_:
estimate = (min_ + max_) // 2
if check(stones, k, estimate) :
min_ = estimate + 1
else:
max_ = estimate
return min_ - 1
from math import factorial
solution = lambda n, k : recur([x for x in range(1, n+1)], k-1)
def recur(nums, k) :
if (n := len(nums)) == 1 :
return [nums.pop()]
index, rest = divmod(k, factorial(n-1))
return [nums.pop(index)] + recur(nums, rest)
from collections import Counter
def solution(a):
elements = Counter(a).most_common()
answer = 0
for k, v in elements:
if v <= answer : break
star = 0
idx = 0
while idx < len(a)-1:
if k not in a[idx:idx+2] or (a[idx] == a[idx+1]):
idx += 1
continue
star += 1
idx += 2
answer = max(star, answer)
return answer * 2
import bisect
def solution(n, works):
works.sort()
for _ in range(n) :
max_num = works.pop(-1)
if max_num < 1 :
return 0
bisect.insort_left(works, max_num-1)
return sum(x**2 for x in works)