""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/76503 """ # 풀이 과정 """ 생각방향: 리프노드를 모두 0으로 만든 후의 생각 접근 핵심 접근 생각 방향 시작:한 곳으로 모으기 생각 #각 점이 간선의 개수가 많은 곳으로 옮기기 #각 점이 간선의 개수가 같다면 가중치가 많은 쪽으로 이동 #위의 두 개 조차 같다면 번호가 작은쪽으로 # 모든 점들이 서로 연결되지 않은 경우 생각해서 체크 필요 # 한 곳으로 모으기 vs 여러 곳으로 나눠모으기 목표:모든 점들의 가중치를 0으로 만들기 """ from collections import defaultdict from collections import deque import sys sys.setrecursionlimit(10 ** 6) # 간선 연결 확인 m = defaultdict(list) result = 0 def dfs(c, p, a): global m, result for up in m[c]: if up != p: dfs(up, c, a) a[p] += a[c] result += abs(a[c]) return result def solution(a, edges): global m, result for i, j in edges: m[i].append(j) m[j].append(i) # a: 각 점의 가중치를 의미 edges: 간선 n = len(a) if sum(a) != 0: return -1 dfs(0, 0, a) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/154539 """ # 풀이 과정 def solution(numbers): stack = [] answer = [-1] * len(numbers) for i in range(len(numbers)): while stack and numbers[stack[-1]] < numbers[i]: answer[stack.pop()] = numbers[i] stack.append(i) return answer

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42893 """ # 풀이 과정 """ 조건: 기본점수: 검색어가 등장하는 횟수 외부링크 수:다른 외부 페이지와 연결된 개수 링크점수:기본점수/외부링크 수 총합 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다. """ from collections import defaultdict from collections import deque import re def solution(word, pages): mylink = defaultdict(list) linkbasic = defaultdict(int) url_list = [] # 기본점수, 외부 링크점수 check = [[0] * 2 for i in range(len(pages))] # 웹페이지별 구분 linkpage = [] # 내부 링크 구분 및 링크 정리 > linkpage for n in range(len(pages)): url = re.search('<meta property=\"og:url\" content=\"https://([\S]+)\".*/>', pages[n]).group(1) linkpage.append(url) url_list.append(url) page = re.findall('<a href=\"https://([\S]+)\">', pages[n]) if len(page) > 0: mylink[url] = page else: mylink[url] = [] # if page is None: # check[n][1]=0 # else: # check[n][1]=len(page) count = 0 for w in re.findall('[a-zA-Z]+', pages[n]): if w.upper() == word.upper(): count += 1 linkbasic[url] = count # mylink=defaultdict(list) # linkbasic=defaultdict(int) result = -1 final = defaultdict(int) for my, another in mylink.items(): # 홍보를 받는 다른 곳 for link in another: if len(mylink[my]) > 0: final[link] += linkbasic[my] / len(mylink[my]) final[my] += linkbasic[my] for r in range(len(url_list)): if final[url_list[r]] > result: result = final[url_list[r]] answer = r return answer

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/118667 """ # 풀이 과정 def solution(queue1, queue2): from collections import deque queue1, queue2 = deque(queue1), deque(queue2) a, b = sum(queue1), sum(queue2) k = a + b if k % 2 == 1: return -1 else: c = k / 2 if a == c: return 0 d = (len(queue1) + len(queue2)) count = 0 while count <= 2 * d: if a < c: t = queue2.popleft() queue1.append(t) a = a + t b = b - t count += 1 elif a > c: t = queue1.popleft() queue2.append(t) a = a - t b = b + t count += 1 elif a == c: return count return -1

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42627 """ # 풀이 과정 # 대기 시간을 줄이기,[요청시점, 소요시간] import heapq from collections import deque def solution(jobs): all_work = len(jobs) operation = [] jobs.sort() j = deque(jobs) time = 0 # 진행중인 작업 now = [] finish = len(jobs) result = [] while finish > 0: # 현재 시간에 따른 들어온 작업 구분 while j: w = j.popleft() if w[0] <= time: now.append(w) else: j.appendleft(w) break # 들어온 작업이 없을 경우 시간 추가 if len(now) == 0: time += 1 continue # 새로운 작업 구성 new = [] for work in now: heapq.heappush(new, [time + work[1], work]) while new: a, b = heapq.heappop(new) command, command_finish = b[0], b[1] time += b[1] result.append(time - b[0]) # 완료된 작업 제거 k = now.index(b) del now[k] finish -= 1 if len(j) > 0: if time >= j[0][0]: break return sum(result) // all_work

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/181187 """ # 풀이 과정 def solution(r1, r2): count = 0 for x in range(1, r2 + 1): a = (r2 ** 2 - x ** 2) ** 0.5 b = 0 if x > r1 else (r1 ** 2 - x ** 2) ** 0.5 if a - b <= 1: if int(a) == a and int(b) != b: count += 1 elif int(a) != a and int(b) == b: count += 1 elif int(a) == 0 and int(b) == 0: count += 1 else: count += int(a) - int(b) elif a - b >= 1 and int(a) == a and int(b) == b: count += int(a) - int(b) + 1 elif a - b >= 1 and int(b) == b: count += int(a) - int(b) + 1 elif a - b >= 1 and int(a) == a: count += int(a) - int(b) else: count += int(a) - int(b) return count * 4

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/118669 """ # 풀이 과정 # 조건: 1~n번의 지점: 출입구 ,쉼터, 산봉우리 중 하나 # intensity:휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 의미 # 출입구는 처음 끝 한번씩 산봉우리 한 번 포함하는 다시 원래 출입구로 돌아오는 등산코스 다른 출입구 한 번더 반복 x # 거리 가중치 최소화를 처음 보고 든 생각 다익스트라 알고리즘 # 출입구와 산봉우리를 제외하면 모두 휴식터로 분류한다 # 지점 수:n 등산로 정보:paths 출입구 정보: gates 산봉우리들 번호:summits # [intensity 최소로 만드는 산봉우리, 그 때의 intensity] 산봉우리가 여러 개 일시 가장 낮은 번호의 산봉우리 # 목표: intensity가 최소가 되도록 등산 코스 정하기 # 생각 방향 등산로를 만들면서 쉼터,산봉우리 갈 시 intensity 재갱신 후 최대로 된 걸 체크 # dfs로 산을 오른 후 경로에 따라 피로도 중 최대를 재갱신 후 산봉우리 도착과 입구와 출구와 같은 지점을 결고값에 넣은 후 # 그 중 sort 이후 최소 값을 답으로 낸다 # 한 번에 여러 조건을 검증하기 보다 출입구로 다시 돌아오는 경로만 추린 후 (if문이 너무 여러 번 쓰여 오히려 복잡해진다) # 다시 경로 재정제하는 방향으로 전환 # dfs로 할 시 중복되는 부분들에 대한 리스트 정리 생각 부족 # dfs 사용시 서로 연결 된 경로가 중복된 경우에 대한 개념 정리 # 산 정상까지만 계산 후 피로도를 계산하면 나머지는 할 필요가 없다 (절반은 반복이니까) from heapq import heappop, heappush from collections import defaultdict from collections import deque import sys sys.setrecursionlimit(10 ** 6) result = [float("inf"), float("inf")] """ def Dijkstra(q,m,s,v): global result while q: # 출발할 위치, 피로도 tired,k=heapq.heappop(q) if tired > v[k] or k in s: continue # if k in s: # if result[1]>tired: # result[0],result[1]=k,tired # elif result[1]==tired: # result[0]=min(k,result[0]) # continue #j: 연결된 경로 i:피로도 for i,j in m[k]: new=max(tired,i) if new<v[j]: v[j]=new q=list(q) heapq.heappush(q,(new,j)) #print(v) return v """ # m:경로 start:시작 지점 s:산봉우리 i:피로도 top:도착한 산봉우리 g:출입구 def solution(n, paths, gates, summits): summits.sort() s = set(summits) # p=paths # g=gates # s=summits def Dijkstra(): global result # 거리 d = defaultdict(list) # 경로 m = defaultdict(list) # check=[float("inf") if not _ in gates else 0 for _ in range(n+1)] check = [float("inf")] * (n + 1) # for i in g: # check[i]=0 # 등산로 별 시간 기록 # for a,b,c in p: # d[(a,b)]=c # d[(b,a)]=c # heapq.heappush(m[a],b) # heapq.heappush(m[b],a) for a, b, c in paths: m[a].append((c, b)) m[b].append((c, a)) q = [] for start in gates: heappush(q, (0, start)) check[start] = 0 # ---------------# v = check while q: # 출발할 위치, 피로도 tired, k = heappop(q) if k in s or tired > v[k]: continue # if k in s: # if result[1]>tired: # result[0],result[1]=k,tired # elif result[1]==tired: # result[0]=min(k,result[0]) # continue # j: 연결된 경로 i:피로도 for i, j in m[k]: new = max(tired, i) if new < v[j]: v[j] = new heappush(q, (new, j)) # print(v) for top in summits: if result[1] > check[top]: result[0], result[1] = top, check[top] return result # check=Dijkstra() # for top in summits: # if result[1]>check[top]: # result[0],result[1]=top,check[top] # elif result[1]==check[top]: # result[0]=min(result[0],top) # finish=sorted(result,key=lambda x:(x[1],x[0])) return Dijkstra()

""" 출처:프로그래머스, 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