Coding
- 무지의 먹방 라이브 p.316
- 문자열 압축 p. 323
- 자물쇠와 열쇠 p.325
- 기둥과 보 설치 p.329
- 외벽 점검 p.335
- 괄호 변환 p.346
- 블록 이동하기 p.355
- 실패율 p.361
- 가사 검색 p.370
- Greedy 접근 방식
import heapq
def solution(food_times, k):
if sum(food_times) <= k :
return -1
q = []
for i in range(len(food_times)):
heapq.heappush(q,(food_times[i],i+1))
sum_value = 0
previous = 0
length = len(food_times)
while sum_value + ((q[0][0] - previous) * length) <= k:
now = heapq.heappop(q)[0]
sum_value += (now - previous) * length
length -=1
previous = now
result = sorted(q,key = lambda x: x[1])
return result[(k - sum_value) % length][1]
solution([3,1,2],5)
cost = [19,78,27,18,20]
sorted(cost)
q = []
for i in range(len(cost)):
heapq.heappush(q,(cost[i],i))
q
len(q)
q[1]
sorted(q,reverse = True)
len(q)
q[0][0]
18 % (10**9 + 7)
def solution(cost, x):
# Write your code here
color1 = 0
color2 = 0
x1 = x
q = []
for i in range(len(cost)):
heapq.heappush(q,(cost[i],i))
q1 = sorted(q,reverse = True)
qq = []
for i in range(len(cost)):
heapq.heappush(qq,(i,cost[i]))
qq1 = sorted(qq,reverse = True)
if x == sum(cost):
for i in range(len(cost)):
color1 += 2**(i)
color2 += 2**(i)
elif x < q1[0][0]:
for i in range(len(q1)):
if x < q1[i][0]:
color1 += 0
else:
color1 += 2**q1[i][1]
x -= q1[i][0]
elif x1 > qq1[0][1]:
for i in range(len(qq)):
if x1 < qq1[i][1]:
color2 += 0
else:
color2 += 2**qq1[i][0]
x1 -= qq1[i][1]
return max(color1, color2) % (10**9 + 7)
solution([3,4,1],8)
solution([19,78,27,18,20],20)
solution([19,78,27,18,20,22,21,90],200)
cost = [19,78,27,18,20,22,21,90]
qq = []
for i in range(len(cost)):
heapq.heappush(qq,(i,cost[i]))
qq1 = sorted(qq,reverse = True)
qq1
qq1[0][1]
2**qq1[0][0]
qq1[0][1]
200-90
2
0 + 1 + 2 = 3
3
2**q[2][1]
eee=[]
heapq.heappush(eee,20)
heapq.heappush(eee,0)
heapq.heappush(eee,30)
eee
heapq.heappop(eee)
def solution(s):
answer = len(s)
for step in range(1,len(s) // 2 + 1):
compressed = ""
prev = s[0:step]
count = 1
for j in range(step, len(s), step):
if prev == s[j:j + step]:
count += 1
else:
compressed += str(count) + prev if count >= 2 else prev
prev = s[j:j + step]
count = 1
compressed += str(count) + prev if count >=2 else prev
answer = min(answer, len(compressed))
return answer
solution('aaabbabababbd')
7%(10**9 + 7)
def rotate_a_matrix_by_90_degree(a):
n = len(a)
m = len(a[0])
result = [[0] * n for _ in range(m)]
for i in range(n):
for j in range(m):
result[j][n - i - 1] = a[i][j]
return result
def check(new_lock):
lock_length = len(new_lock) // 3
for i in range(lock_length, lock_length * 2):
for j in range(lock_length, lock_length * 2):
if new_lock[i][j] != 1:
return False
return True
def solution(key, lock):
n = len(lock)
m = len(key)
new_lock = [[0] * (n * 3) for _ in range(n * 3)]
for i in range(n):
for j in range(n):
new_lock[i + n][j + n] = lock[i][j]
for rotation in range(4):
key = rotate_a_matrix_by_90_degree(key)
for x in range(n * 2):
for y in range(n * 2):
for i in range(m):
for j in range(m):
new_lock[x+ i][y + j] += key[i][j]
if check(new_lock) == True:
return True
for i in range(m):
for j in range(m):
new_lock[x+i][y+j] -= key[i][j]
return False
solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],[[1, 1, 1], [1, 1, 0], [1, 0, 1]])
def possible(answer):
for x, y, stuff in answer:
if stuff == 0:
if y == 0 or [x - 1, y, 1] in answer or [x,y,1] in answer or [x, y - 1, 0] in answer:
continue
return False
elif stuff == 1:
if [x, y - 1 ,0] in answer or [x+1,y-1,0] in answer or ([x-1, y,1] in answer and [x + 1, y,1] in answer):
continue
return False
return True
def solution(n, build_frame):
answer = []
for frame in build_frame:
x,y,stuff,operate = frame
if operate == 0:
answer.remove([x,y,stuff])
if not possible(answer):
answer.append([x,y,stuff])
if operate == 1:
answer.append([x,y,stuff])
if not possible(answer):
answer.remove([x,y,stuff])
return sorted(answer)
solution(5,([1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]))
solution(5,([0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]))
from itertools import permutations
def solution(n, weak, dist):
length = len(weak)
for i in range(length):
weak.append(weak[i] + n)
answer = len(dist) + 1
for start in range(length):
for friends in list(permutations(dist,len(dist))):
count = 1
position = weak[start] + friends[count - 1]
for index in range(start, start + length):
if position < weak[index]:
count += 1
if count > len(dist):
break
position = weak[index] + friends[count - 1]
answer = min(answer, count)
if answer > len(dist):
return -1
return answer
solution(12,[1, 5, 6, 10],[1, 2, 3, 4])
solution(12,[1, 3, 4, 9, 10],[3, 5, 7])
DFS 알고리즘
def balanced_index(p):
count = 0
for i in range(len(p)):
if p[i] == '(':
count += 1
else:
count -= 1
if count == 0:
return i
def check_proper(p):
count = 0
for i in p:
if i == '(':
count += 1
else:
if count == 0:
return False
count -= 1
return True
def solution(p):
answer = ''
if p == '':
return answer
index = balanced_index(p)
u = p[:index + 1]
v = p[index + 1:]
if check_proper(u):
answer = u + solution(v)
else:
answer = '('
answer += solution(v)
answer += ')'
u = list(u[1:-1])
for i in range(len(u)):
if u[i] == '(':
u[i] = ')'
else:
u[i] = '('
answer += "".join(u)
return answer
solution('(()())()')
solution(')(')
solution('()))((()')
BFS 유형
from collections import deque
def get_next_pos(pos,board):
next_pos = []
pos = list(pos)
pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y + dy[i], pos2_x + dx[i], pos2_y + dy[i]
if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
next_pos.append({(pos1_next_x,pos1_next_y),(pos2_next_x, pos2_next_y)})
if pos1_x == pos2_x:
for i in [-1,1]:
if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y] == 0:
next_pos.append({(pos1_x,pos1_y),(pos1_x + i, pos1_y)})
next_pos.append({(pos2_x,pos2_y),(pos2_x + i, pos2_y)})
elif pos1_y == pos2_y:
for i in [-1,1]:
if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y + i] == 0:
next_pos.append({(pos1_x,pos1_y),(pos1_x, pos1_y + i)})
next_pos.append({(pos2_x,pos2_y),(pos2_x, pos2_y + i)})
return next_pos
def solution(board):
n = len(board)
new_board = [[1] * (n + 2) for _ in range(n + 2)]
for i in range(n):
for j in range(n):
new_board[i + 1][j + 1] = board[i][j]
q = deque()
visited = []
pos = {(1,1),(1,2)}
q.append((pos,0))
visited.append(pos)
while q:
pos, cost = q.popleft()
if (n,n) in pos:
return cost
for next_pos in get_next_pos(pos,new_board):
if next_pos not in visited:
q.append((next_pos, cost + 1))
visited.append(next_pos)
return 0
solution([[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]])
O(NlogN)
def solution(N,stages):
answer = []
length = len(stages)
for i in range(1, N+1):
count = stages.count(i)
if length ==0:
fail = 0
else:
fail = count / length
answer.append((i, fail))
length -= count
answer = sorted(answer, key=lambda t: t[1], reverse = True)
answer = [i[0] for i in answer]
return answer
solution(5,[2, 1, 2, 6, 2, 4, 3, 3])
solution(4,[4,4,4,4,4])
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a,left_value)
return right_index - left_index
array = [[] for _ in range(10001)]
reserved_array = [[] for _ in range(10001)]
def solution(words, queries):
answer = []
for word in words:
array[len(word)].append(word)
reserved_array[len(word)].append(word[::-1])
for i in range(10001):
array[i].sort()
reserved_array[i].sort()
for q in queries:
if q[0] != '?':
res = count_by_range(array[len(q)], q.replace('?','a'), q.replace('?','z'))
else:
res = count_by_range(reserved_array[len(q)], q[::-1].replace('?','a'),q[::-1].replace('?','z'))
answer.append(res)
return answer
solution(["frodo", "front", "frost", "frozen", "frame", "kakao"],["fro??", "????o", "fr???", "fro???", "pro?"])
array = [[] for _ in range(10001)]
3 - 3//2
def solution(x, y, z):
# Write your code here
if x > y:
if x - z == y:
answer = x
elif x - z != y and z % 2 == 0:
answer = x
elif x - z != y and (z - (x - y)) % 2 == 0:
answer = x + (z-(x-y))//2
else:
answer = -1
elif x <= y:
if x + z == y:
answer = y
elif x + z != y and z % 2 == 0:
answer = x + z//2
elif x + z != y and (z + (y - x)) % 2 == 0:
answer = x + (z-(y-z))//2
else:
answer = -1
return answer
solution(5,8,7)
4//2
solution(8,5,3)
solution(3,4,6)
// 2
2**2
sum([1,1])
box = [5, 15, 19]
box = [1,5,7,6]
box = [10,3,5,7]
len(box)
sum(box)
sum(box) // len(box)
q = []
for i in range(len(box)):
heapq.heappush(q,(box[i],i+1))
q = sorted(q,reverse=True)
q
max(q)
def solution(box):
# Write your code here
q = []
for i in range(len(box)):
heapq.heappush(q,(box[i],i+1))
q = sorted(q,reverse=True)
if q[0][1] >= 2 :
boxresult = sum(box) // len(box)
else:
boxresult = max(box)
return boxresult
def solution(box):
# Write your code here
q = []
for i in range(len(box)):
heapq.heappush(q,(box[i],i+1))
q = sorted(q,reverse=True)
if q[0][1] >= 2 and (sum(box) / len(box) ) * (len(box) -1) != int((sum(box) / len(box) ) * (len(box) -1) ):
boxresult = sum(box) - int((sum(box) / len(box) ) * (len(box) -1) )
if q[0][1] >= 2 and (sum(box) / len(box) ) * (len(box) -1) == int((sum(box) / len(box) ) * (len(box) -1) ):
boxresult = sum(box) // len(box)
else:
boxresult = max(box)
return boxresult
box = [3,8,11,7]
sum(box)
(sum(box) / len(box) ) * (len(box) -1)
(sum(box) / len(box) ) * (len(box) -1) == int((sum(box) / len(box) ) * (len(box) -1) )
sum(box) - int((sum(box) / len(box) ) * (len(box) -1) )
sum(box) // len(box) , sum(box) % len(box)
8
box = [1,5,7,6]
sum(box) // len(box) , sum(box) % len(box)
box = [5,15,19]
sum(box) // len(box) , sum(box) % len(box)
solution(box)
q = []
for i in range(len(box)):
heapq.heappush(q,(box[i],i+1))
q = sorted(q,reverse=True)