본문 바로가기

DC 228

[자료구조] 등굣길 파이썬 (DP) def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] # first row and colum are 1 for i in range(n+1): for j in range(m+1): if i == 1 or j == 1: dp[i][j] = 1 if i == 0 or j == 0: dp[i][j] = 0 if m 2021. 4. 26.
[자료구조] 빙고 파이썬 (hash,list comprehension) def solution(board, nums): n = len(board) # board의 길이 nums = dict.fromkeys(nums, True) # nums 리스트 값을 키로 변환하여 dict로 만들어준다, # nums = {14: True, 3: True, ... , 5: True, 15: True} row_list = [0] * n col_list = [0] * n left_diagonal = 0 right_diagonal = 0 for i in range(n): # O(n) for j in range(n): # O(n) if board[i][j] in nums: # O(1) board[i][j] = 0 # make it checked row_list[i] += 1 col_list[j] +.. 2021. 4. 26.
[자료구조] 야근 수당 파이썬 (heap) from heapq import heapify, heappush, heappop from collections import deque def solution(n, works): if n > sum(works): return 0 works = [(-i,i) for i in works] heapify(works) for _ in range(n): w = heappop(works)[1] - 1 heappush(works, (-w,w)) ################ # print works # while works: # w = heappop(works) # print(w) return sum(i[1]**2 for i in works) max value를 하나씩 -1 해줄 것이기 때문에 max heap를 구성해.. 2021. 4. 25.
[자료구조] 게임 아이템 파이썬 (heap, deque) 해답 from heapq import heapify, heappush, heappop from collections import deque def solution(healths, items): healths.sort() # 체력을 오름차순으로 정렬 items = sorted([(item[1], item[0], index+1) for index, item in enumerate(items)]) # 깎는 체력 순으로 정렬 items = deque(items) answer = [] heap = [] for health in healths: # 제일 작은 체력부터 루프 while items: # 아이템 루프 debuff, buff, index = items[0] # 가장 깎는 체력이 낮은 아이템 if healt.. 2021. 4. 25.
[자료구조] 방문 길이 파이썬 (hash) def solution(dirs): x,y = 5,5 # start point mapping = {"U":(0,1), "D":(0,-1), "R":(1,0), "L":(-1,0)} visited = [[0 for _ in range(11)] for _ in range(11)] for i,d in enumerate(dirs): if 0 2021. 4. 24.
[자료구조] FloodFill 파이썬 (BFS, queue) BFS from collections import deque def solution(n, m, image): cnt = 0 visited = [[False] * m for _ in range(n)] # visited table (col(m) x row(n)) dir = [[1,0], [0,1], [-1,0], [0,-1]] # 4-direction for i in range(n): for j in range(m): if not visited[i][j]: q = deque() # BFS-queue q.append([i,j]) visited[i][j] = True color = image[i][j] while q: x, y = q.popleft() for dx, dy in dir: xx, yy = x+dx,.. 2021. 4. 23.
[자료구조] 배달 파이썬 (BFS, queue, Dijkstra, heap) from math import inf from collections import defaultdict, deque from itertools import product def solution(N, roads, K): answer = [inf, 0] + [inf for i in range(N-1)] # print(answer) # why 처음이 0이 아니라 inf로 설정했을까? -> zero 인덱스 문제를 편하게 하려고 map = defaultdict(list) # 리스트 형태로 받겠다. dist_map = [[inf for _ in range(N+1)] for _ in range(N+1)] # print(dist_map) # for road in roads: a,b,dist = road map[a].ap.. 2021. 4. 23.
[자료구조] 문자열 압축 사본 파이썬 (👍) def solution(s): if len(s) == 1: return 1 res = [] cut_range = list(range(1, (len(s)//2)+1)) ans = "" for cut in cut_range: tmp = s[:cut] cnt = 1 for i in range(cut, len(s), cut): if tmp == s[i:i+cut]: cnt += 1 else: if cnt == 1: cnt = "" ans += str(cnt) + tmp cnt = 1 tmp = s[i:i+cut] if cnt == 1: cnt = "" ans += str(cnt) + tmp res.append(len(ans)) ans = "" return min(res) 저번에도 한번 도전했었는데 이번에도 역시.. 2021. 4. 23.
[자료구조] 주사위 게임 파이썬 (product) from itertools import product def solution(monster, S1, S2, S3): l1 = list(range(1, S1+1)) l2 = list(range(1, S2+1)) l3 = list(range(1, S3+1)) prod = list(map(sum,product(l1, l2, l3))) print(prod) cnt = 0 for p in prod: if p + 1 in monster: cnt += 1 return int((len(prod)-cnt)/len(prod)*1000) 출처: velog.io/@rapsby/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A3%BC%EC%82%AC%EC%9C%84-%.. 2021. 4. 23.

티스토리툴바