3주차
- Day15 | 등굣길 #107, Two Sum #108
- Day16 | 징검다리 #107
- Day17 | 순위 #116
- Day18 | 위장 #121, 프린터 #122
- Day19 | 이중우선순위큐 #127, 카펫 #128
- Day20 | 선 연결하기 #133
- Day21 | 방의 개수 #138
등굣길
to be continued ,,,
def main():
print(solution(4,3,[[2,2]]))
def solution(m, n, puddles):
dp = [[0 for j in range(m+1)] for i in range(n+1)]
dp[1][1] = 1
for x,y in puddles:
dp[y][x] = -1
for i in range (1,n+1):
for j in range(1,m+1):
if dp[i][j] == -1 :
dp[i][j] = 0
continue
dp[i][j] += (dp[i-1][j]+dp[i][j-1]) % 1000000007
return dp[n][m]
if __name__ == "__main__":
main()Two Sum
Leet Code
to be continued ,,,
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
answer = []
for i in range(len(nums)):
j = i+1
for j in range(j,len(nums)):
if nums[i] + nums[j] == target:
answer.append(i)
answer.append(j)
return answer징검다리
제거할 위치 기준으로 이분 탐색
while(start ≤ end):
mid = (start + end) // 2
def main():
print(solution(25,[2, 14, 11, 21, 17],2))
def solution(distance, rocks, n):
answer = 0
rocks.sort()
start=0
end=distance
while(start <= end):
mid=(start+end)//2
cnt = 0 # 제거할 돌
i = 0 # 기준 돌
for j in range(len(rocks)):
if rocks[j] - i < mid:
cnt += 1
else:
i = rocks[j]
if cnt > n:
break;
if cnt <= n:
start = mid + 1
answer = mid
else:
end = mid -1
return answer
if __name__ == "__main__":
main()순위
인접행렬 만들어서 ???
def main():
solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]])
def solution(n, results):
answer = 0
board = [[0]*n for _ in range(n)]
for a,b in results:
board[a-1][b-1] = 1
board[b-1][a-1] = -1
for k in range(n):
for i in range(n):
for j in range(n):
if i == j or board[i][j] in [1,-1]:
continue
if board[i][k] == board[k][j] == 1:
board[i][j] = 1
board[j][i] = board[k][i] = board[j][k] = -1
for i in board:
if i.count(0) == 1:
answer += 1
return answer
if __name__ == "__main__":
main()위장
to be continued ,,,
def main():
print(solution([["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]))
def solution(clothes):
arr = {}
for c, type in clothes:
arr[type] = arr.get(type, 0) + 1
answer = 1
for type in arr:
answer *= (arr[type] + 1)
return answer - 1
if __name__ == "__main__":
main()프린터
to be continued ,,,
def main():
print(solution([2, 1, 3, 2],2))
def solution(priorities, location):
answer = 1
m = max(priorities)
while True:
temp = priorities.pop(0)
if temp == m :
if location == 0:
return answer
answer += 1
location -= 1
m = max(priorities)
else:
priorities.append(temp)
if location == 0:
location = len(priorities ) -1
else:
location -= 1
if __name__ == "__main__":
main()이중우선순위 큐
to be continued ,,,
def main():
print(solution(["I -45", "I 653", "D 1", "I -642", "I 45",
"I 97", "D 1", "D -1", "I 333"]))
def solution(operations):
answer = [0,0]
que = []
for oper in operations:
c,n=oper.split(" ")
if c == 'I':
que.append(int(n))
elif c == 'D':
if que:
if n == '1' :
que.remove(max(que))
elif n == '-1':
que.remove(min(que))
if que:
answer[0] = max(que)
answer[1] = min(que)
else:
answer[0] = 0
answer[1] = 0
return answer
if __name__ == "__main__":
main()카펫
완전탐색
def main():
print(solution(10,2))
def solution(brown,yellow):
answer = [0,0]
num = brown + yellow
for i in range(1,num+1):
row = i
col = num //row
if(row > col):
continue
if((row -2)*(col -2) == yellow):
answer[0] = col
answer[1] = row
return answer
return answer
if __name__ == "__main__":
main()섬 연결하기
방의 개수
오일러공식
💡 꼭짓점 개수 (v) - 모서리 개수 (e) + 면 개수(f) = 1면 개수(f) = 1 + 모서리 개수 (e) - 꼭짓점 개수 (v)
def solution(arrows):
# f = 1 + e - v
e = set()
v = {(0,0)}
dx = [0,1,1,1,0,-1,-1,-1]
dy = [1,1,0,-1,-1,-1,0,1]
x=y=nx=ny=0
for a in arrows:
for _ in range(2):
nx = x+dx[a]
ny = y+dy[a]
v.add((nx,ny))
e.add(frozenset({(nx,ny),(x,y)}))
x,y = nx,ny
return 1 + len(e) - len(v)