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)
import re
from itertools import permutations
def check(banned_permutations, patterns) :
for pattern, ban_id in zip(patterns, banned_permutations) :
if not pattern.fullmatch(ban_id) :
return False
return True
def solution(user_id, banned_id):
answer = []
patterns = [re.compile(x.replace('*', '.')) for x in banned_id]
for banned_permutations in permutations(user_id, len(banned_id)):
if check(banned_permutations, patterns) and set(banned_permutations) not in answer:
answer.append(set(banned_permutations))
return len(answer)
Lv.5 방의갯수문제와 90% 이상 비슷한 문제다.
from collections import defaultdict
add = lambda x, y : (x[0]+y[0], x[1]+y[1])
check = lambda point, next_point, dir_ : (move[dir_][2] not in points[next_point]) and (dir_ not in points[point])
def solution(dirs):
global points, move
answer = 0
move = {'U':(-1, 0, 'D'), 'R':(0, 1, 'L'), 'D':(1, 0, 'U'), 'L':(0, -1,'R')}
points = defaultdict(set)
point = (0, 0)
for dir_ in dirs :
next_point = add(point, move[dir_])
if not(-5<=next_point[0]<=5 and -5<=next_point[1]<=5) :
continue
answer += 1 if check(point, next_point, dir_) else 0
points[point].add(dir_)
point = next_point
return answer