-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/258711 """ # 풀이 과정 def solution(edges): result = [0, 0, 0, 0] g = {} e = edges # 용어 축소 for start, arrive in e: # g[0]:start g[1]:arrive if not g.get(start): g[start] = [0, 0] if not g.get(arrive): g[arrive] = [0, 0] g[start][0] += 1 g[arrive][1] += 1 for key, val in g.items(): # 정점 찾기 if val[0] >= 2 and val[1] == 0: result[0] = key # 막대그래프 찾기 elif val[0] == 0 and val[1] >= 1: result[2] += 1 # 8자그래프 찾기 elif val[0] >= 2 and val[1] >= 2: result[3] += 1 # 도넛 그래프 result[1] = (g[result[0]][0] - result[2] - result[3]) return result
-
# 생각의 포인트 """ 츌처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/133500 생각의 전제: 트리 내 전체 등대는 모두 켜져야 한다 자식 노드와 부모 노드와의 관계성에서 부모노드가 켜지면 자식노드는 켜지든 꺼지는 상관없다 부모노드가 꺼지면 자식노드는 무조건 켜져야 부모 노드 또한 밝음 유지 # 전체 등대가 켜져야한다는 생각을 지닌채로 dfs 실행 후 맨 아래 리프 노드부터 맨 위의 루트노드까지의 생각을 이어나가야 풀 수 있다. 코드의 흐름은 전체 내려가면서 모두가 켜지는 상황을 구현 그리고 맨 아래로 리프노드로 내려 갈 시 그 맨 위의 등대가 어떻게해야 최소로 등대를 켤 수 있는지를 고려해야한다 dfs는 맨 아래 리프 노드에 대한 생각을 맨 위로 끌어올리는게 포인트! 최대 깊이 설정에 대한 것도 생각 import sys sys.setrecursionlimit(10 ** 6) 위의 라이브러리를 사용 안할시 깊이 문제로 오류 발생 """ # 풀이 과정 # dfs 깊이 설정 from collections import defaultdict import sys sys.setrecursionlimit(10 ** 6) m = defaultdict(list) def dfs(k, check): check[k] = True # 해당 노드는 on light, black = 1, 0 # 해당 노드가 켜질 때 꺼질 때 for next_node in [n for n in m[k] if check[n] != True]: next_node_light, next_node_black = dfs(next_node, check) light += min(next_node_light, next_node_black) # 다 켜지는 상황에서의 next 노드의 light,black 생각 밑바탕! black += next_node_light return light, black def solution(n, lighthouse): l = lighthouse check = [False] * (n + 1) # 등대 번호 for start, arrive in l: m[start].append(arrive) m[arrive].append(start) light, black = dfs(1, check) return min(light, black)
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42626 """ # 풀이 과정 def solution(scoville, K): import heapq t = scoville heap = [] result = 0 # for문 len(t) 개수만큼이라 t.sort()로 한 후 시작한거랑 동일! while t: a = t.pop() heapq.heappush(heap, a) while heap: a = heapq.heappop(heap) if a < K: if len(heap) > 0: result += 1 b = heapq.heappop(heap) count = (a + b * 2) heapq.heappush(heap, count) else: return -1 # 다 섞어도 k 못넘음 else: break return result
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42898 """ # 풀이과정 from collections import deque def solution(m, n, puddles): puddles = set(list(map(tuple, puddles))) check = [[0] * (m + 1) for _ in range(n + 1)] for i in range(2, m + 1): if not (i, 1) in puddles: check[1][i] = 1 else: break for j in range(2, n + 1): if not (1, j) in puddles: check[j][1] = 1 else: break for i in range(2, n + 1): for j in range(2, m + 1): if not (j, i) in puddles: check[i][j] = check[i - 1][j] + check[i][j - 1] else: check[i][j] = 0 return check[n][m] % 1000000007
-
""" 출처: 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/169198 """ # 풀이 과정 def solution(m, n, startX, startY, balls): result = [] for x, y in balls: check = [] # 아래벽 if startY >= y and startX == x: pass else: d_1 = ((abs(startX - x) ** 2 + abs(-startY - y) ** 2)) check.append(d_1) # 왼쪽벽 if startX >= x and startY == y: pass else: d_2 = ((abs(-startX - x) ** 2 + abs(startY - y) ** 2)) check.append(d_2) # 위쪽벽 if startY <= y and startX == x: pass else: d_3 = ((abs(startX - x) ** 2 + abs(2 * n - startY - y) ** 2)) check.append(d_3) # 오른쪽벽 if startX <= x and startY == y: pass else: d_4 = ((abs(2 * m - startX - x) ** 2 + abs(startY - y) ** 2)) check.append(d_4) # 왼쪽 사이드 d_5 = ((abs(-startX - x) ** 2 + abs(-startY - y) ** 2)) check.append(d_5) # 왼쪽 위 사이드 d_6 = ((abs(-startX - x) ** 2 + abs(2 * n - startY - y) ** 2)) check.append(d_6) # 오른쪽 위 사이드 d_7 = ((abs(2 * m - startX - x) ** 2 + abs(2 * n - startY - y) ** 2)) check.append(d_7) # 오른쪽 아래 사이드 d_8 = ((abs(2 * m - startX - x) ** 2 + abs(-startY - y) ** 2)) check.append(d_8) result.append(min(check)) return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/43163 """ # 풀이 과정 from collections import deque import copy def solution(begin, target, words): english = list("abcdefghijklmnopqrstuvwxyz") words = set(words) if target not in words: return 0 elif len(target) != len(begin): return 0 max_count = len(begin) result = [] q = deque([(begin, 0)]) check = set([]) check.add(begin) while q: start, count = q.popleft() check.add(start) if start == target: result.append(count) change_words = list(start) for change in range(len(begin)): for eng in english: new = copy.deepcopy(change_words) new[change] = eng new_words = str("".join(new)) if not new_words in check and new_words in words: q.append((new_words, count + 1)) return min(result)
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12911 """ # 풀이 과정 def solution(n): a = bin(n) b = a[2:] c = b.count("1") k = n while True: k += 1 t = bin(k) v = t[2:].count("1") if v == c: return k answer = 0 return answer
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42884 """ # 풀이 과정 from collections import defaultdict from collections import deque import heapq def solution(routes): check = [] car_start = defaultdict(set) car_end = defaultdict(set) for c in range(len(routes)): check.append(routes[c][0]) check.append(routes[c][1]) car_start[routes[c][0]].add(c) car_end[routes[c][1]].add(c) start = min(check) end = max(check) check.sort() now = set([]) result = 0 check_car = set([]) # 이전에 발견되던게 지금 발견 안되면 그 지점은 무조건 카메라 설치 필수 for time in check: now = now | car_start[time] # 빠지는 차량 발생 if len(car_end[time]) > 0: if len(car_end[time] - check_car) > 0: result += 1 check_car = check_car | car_end[time] | now return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42583 """ # 풀이과정 def solution(bridge_length, weight, truck_weights): from collections import deque b_l = bridge_length # 최대 수용 가능 차량 수 w = weight # 무게 t_w = deque(truck_weights) now = 0 # 시간 count_w = 0 # 다리 위 차량 무게 count_c = 0 # 차량 수 check = deque([]) while t_w: k = t_w.popleft() if len(check) == 0: check.append([now, k]) count_w += k count_c += 1 else: if now - check[0][0] == b_l: # 차가 다리를 벗어나는 시점 i, j = check.popleft() count_w -= j count_c -= 1 if count_w + k <= w and count_c + 1 <= b_l: check.append([now, k]) count_w += k count_c += 1 else: t_w.appendleft(k) now += 1 # print(check) continue if count_w + k <= w and count_c + 1 <= b_l: check.append([now, k]) count_w += k count_c += 1 else: t_w.appendleft(k) now += 1 # print(check) return check[-1][0] + b_l + 1
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/77486 """ # 내 풀이 """ 생각방향:등비급수처럼 리스트를 만든 후 맨 위에 지속적으로 더해주는 형태 목표:enroll에 적힌 판매원들의 수익을 출력 """ from collections import defaultdict import math # 판매원 수익 명단 dic check = [] name = [] # 추천인 분배 def divide(e, r, n, p): global check, name # 1원 미만으로 분배금이 떨어질 경우 분배금 발생 x while n >= 1: # 등록자 번호 위치 k = name[p] # 추천인이 없는 경우 if r[k] == "-": break # 추천인이 있는 경우 else: check[r[k]] += math.ceil(n * (0.9)) n = int(n * (0.1)) # 더 위의 상위순번 추천자 시작 p = r[k] return 0 def solution(enroll, referral, seller, amount): global check, name check = defaultdict(int) name = defaultdict(int) for i, j in enumerate(enroll): check[j] = 0 name[j] = i # 구성원 e = enroll # 추천인 찾기 r = referral # 판매 집계 데이터의 판매원 이름 s = seller # 판매 집계 데이터 a = amount for i in range(len(a)): n = a[i] * 100 # 판매량*단가 p = s[i] # 판매원 # 처음 판매자 수익금 가져가기 check[p] += math.ceil((0.9) * (n)) # 분배할 금액 n = int(n * (0.1)) # 구성원 명단,추천인 명단,남은 분배금액, 최초 판매자 divide(e, r, n, p) result = [] for f in enroll: result.append(check[f]) return result
