소민's Blog

가장 먼 노드 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이최소힙으로 1에서부터 각 노드까지의 최단거리를 구해서 Counter로 갯수 셈from collections import defaultdict, Counterimport heapqdef solution(n, edge): answer = 0 graph=defaultdict(list) for eg in edge: x,y=eg graph[x].append(y) graph[y].append(x) hq=[] heapq.heappush(hq,(0,1)) visited=[Fa..

호텔 대실 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이처음에 요격 시스템이랑 유사한 문제라고 생각하고 끝지점으로 정렬 해버림하지만, 요격 시스템이 여러팀을 한번에 처리하는 방식이라면,이번 문제는 각 호텔 방마다 1개의 팀만 가능하기 때문에 아예 다른 문제임 "겹치지 않도록 배정하는 문제" → 시작 시간 기준 정렬"덮거나 포함시키는 문제" → 끝나는 지점 기준 정렬 heap을 이용해서 시작시간이 가장 빠른 방을 찾고가지고 있는 객실 중에 가장 빨리 끝난 방과 시작시간을 비교하면서방을 늘릴지, 해당 방을 쓸지 결정 import heapqdef solution(book_time): time..

야근 지수 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이 n 1,000,000➡ heapq 사용queue가 비어있는지 확인 안하면 런타임에러!!import heapqdef solution(n, works): #피로도: 시작 시점+(남은일의 작업량)**2 answer = 0 queue=[] for work in works: heapq.heappush(queue,-work) while n>=1: if not queue: break tmp=heapq.heappop(queue) if tmp!=0: ..

배달 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import heapq def dijkstra(start, graph, dist): queue=[] heapq.heappush(queue, (dist[start], start)) while queue: cost, node= heapq.heappop(queue) for c, n in graph[node]: if cost+c>=dist[n]: continue dist[n]=cost+c heapq.heappush(queue, (dist[n], n)) def solution(N, road, K): answer ..

베스트 앨범 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫 시도 런타임 에러 import heapq def solution(genres, plays): answer = [] genres_cnt=[] sort_play={} for genre in set(genres): cnt=0 tmp=[] for idx, gp in enumerate(zip(genres, plays)): g,p=gp if g!=genre: continue cnt+=p heapq.heappush(tmp,(-p, idx)) heapq.heappush(genres_cnt, (-cnt, ge..

10282. 해킹 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 내 풀이 다익스트라: heap 써야함 계속 틀린 이유 더 짧은 시간값이 나오면 그와 연결된 값들도 다 업데이트 해줘야하므로 힙에 다시 넣어줘야함!! # a->b 의존 b감염->a감염 import heapq def bfs(start): global result global cnt visited.add(start) result[start]=0 cnt+=1 heapq.heappush(q, (0,start)) while q: time, x =heapq.he..

1238. 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다른 사람 풀이 시작위치, 도착위치, 거리 입력받을 때 graph에 (거리, 도착위치) 순으로 넣기 -> 이후에 heap에도 그렇게 넣을거니까 순서 헷갈리지 않도록 하기 위함 각각의 학생의 최단경로를 모두 구하기위해 for문 돌면서 dijkstra 새로 실행하므로 dijkstra 안에서 distance 초기화 해줘야함 →그리고 distance 배열 자체를 리턴 dijkstra(i) : i번째 마을에서 시작해서 각 마..

1753. 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 내 풀이 - HashMap 이용 key: 시작정점 값 / value: Pair( 도착정점 값, 가중치값) package day18_dijkstra; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class JUN1753_ParkSomin {..