from collections import defaultdict
def fill_black(board, h, w):
board[h][w] = (-1 if h == 0 or board[h - 1][w] == -1 else 0)
def check(block, blocks, board) :
if len(blocks) < 4 : return False
h_list = sorted([h for h, w in blocks])
w_list = sorted([w for h, w in blocks])
for h in range(h_list[0], h_list[-1] + 1):
if any(color not in (-1, block) for color in board[h][w_list[0]:w_list[-1] + 1]):
return False
return True
def solution(board):
blocks = defaultdict(list)
answer = 0
for h in range((n := len(board))) :
for w in range(n) :
if (block := board[h][w]) > 0 :
(block_points := blocks[block]).append((h, w))
if not check(block, block_points, board) :
continue
answer += 1
for bh, bw in block_points :
fill_black(board, bh, bw)
elif block == 0 :
fill_black(board, h, w)
return answer
๊ฐ์ฌ๊ฒ์ ๋ฌธ์ ์ ๋น์ทํจ. Trie Tree ๋ฅผ ์ด์ฉํ ๋ฌธ์
def solution(words):
tree = Trie()
for word in words :
tree.insert(word)
return sum(tree.query(word) for word in words)
class TrieNode:
def __init__(self, char):
self.char = char
self.counter = 0
self.children = {}
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
node.counter += 1
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.counter += 1
def query(self, word) :
node = self.root
for i, char in enumerate(word) :
node = node.children[char]
if node.counter == 1 :
return i+1
return len(word)
from itertools import accumulate
def solution(food_times, k):
n = len(food_times)
food_acc = list(accumulate((f := [0] + sorted(food_times))))
for i in range(1, n+1) :
if food_acc[i] + (n-i)*f[i] > k :
remain_food = [index+1 for index, food in enumerate(food_times) if food >= f[i]]
idx = (k - (food_acc[i-1] + (n-(i-1))*f[i-1])) % (n-(i-1))
return remain_food[idx]
return -1
from itertools import chain
def solution(land, P, Q):
land = sorted(chain.from_iterable(land))
k = len(land) * Q // (P + Q)
h = land[k]
return sum(h - x for x in land[:k])*P + sum(x - h for x in land[k:])*Q
def solution(strs, t):
DP = [0] * ((n := len(t)) + 1)
for i in range(1, n+1) :
DP[i] = min((DP[k] + 1 for k in range(max(0, i - 5), i) if t[k:i] in strs), default = 1e6)
return DP[-1] if DP[-1] < 1e6 else -1
from itertools import accumulate,combinations
def solution(cookie):
acc = set(accumulate([0] + cookie))
answer = [abs(x - y) // 2 for x, y in combinations(acc, 2) if (m := x + y) % 2 == 0 and m // 2 in acc]
return max(answer, default=0)
import sys
sys.setrecursionlimit(10**6)
def solution(k, room_number):
global pointer
pointer = {}
return [check_in(room) for room in room_number]
def check_in(room) :
if room not in pointer :
pointer[room] = room + 1
return room
pointer[room] = (avail := check_in(pointer[room]))
return avail
๋๋์ง ๋ฌธ์ ์ 100% ๋์ผ
def solution(sticker):
if len(sticker) < 3 : return max(sticker) # ์คํฐ์ปค๊ฐฏ์ 3๊ฐ๊ฐ ์๋ ๊ฒฝ์ฐ
x1, y1, z1 = sticker[0], max(sticker[:2]), max(sticker[0]+sticker[2], sticker[1]) #์ฒซ์ง ํฐ๋ ๊ฒฝ์ฐ
x2, y2, z2 = 0, sticker[1], sticker[2] # ์ฒซ์ง ์ํฐ๋ ๊ฒฝ์ฐ
for i in sticker[3:]:
x1, y1, z1 = y1, z1, max(x1, y1)+i
x2, y2, z2 = y2, z2, max(x2, y2)+i
return max(x1, y1, y2, z2)
from math import comb
solution = lambda n : comb(2 * n, n) / (n + 1)
def divisor(m) :
for i in range(2, int(m**0.5)+1) :
if m%i == 0 and (measure := m//i) <= 10000000 : return measure
return 1 if m > 1 else 0
def solution(begin, end):
return [divisor(x) for x in range(begin, end+1)]