from collections import defaultdict
to_minute = lambda time : sum([int(x)*y for x, y in zip(time.split(':'), [60, 1])])
to_time = lambda minute : ':'.join(map('{0:02d}'.format, divmod(minute, 60)))
def solution(n, t, m, timetable):
minute_table = sorted(map(to_minute, timetable))
bus_table = {to_minute('09:00')+t*i:[] for i in range(n)}
for bus in bus_table :
for j in range(m) :
if minute_table and minute_table[0] <= bus :
bus_table[bus].append(minute_table.pop(0))
last_time, last_bus = list(bus_table.items())[-1]
return to_time(last_time) if len(last_bus) < m else to_time(max(last_bus)-1)
from collections import defaultdict
import re
from decimal import Decimal
def solution(word, pages) :
word = word.lower()
web = defaultdict(defaultdict)
link_score = defaultdict(int)
url_pattern = re.compile('<meta property=\"og:url\" content=\"(.+?)"')
body_pattern = re.compile(r'\<body>\n(.+?)\n\</body>', re.S)
ext_url_pattern = re.compile('<a href="(.+?)"')
for index, page in enumerate(pages) :
page = page.lower()
url = url_pattern.findall(page).pop()
web[url]['index'] = index
body = ' '.join(body_pattern.findall(page))
web[url]['ext_url'] = ext_url_pattern.findall(body)
web[url]['basic_score'] = Decimal(str(re.sub('[^a-z]', '.', body).split('.').count(word)))
for ext_url in web[url]['ext_url'] :
link_score[ext_url] += web[url]['basic_score'] / len(web[url]['ext_url'])
return sorted([[val['basic_score'] + link_score[url], val['index']] for url, val in web.items()], key = lambda x : (-x[0], x[1]))[0][1]
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)