이진탐색으로 하나만 정렬하고 bisect으로 찾는 방법이 있고 투 포인터로 둘 다 정렬한 다음 같이 인덱스 0으로 시작해서 작은 배열의 인덱스를 1씩 증가시키는 방법이 있다. 중복이 없어야 되므로 set()을 사용한다 class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() nums2.sort() result=set() i=j=0 while i
from collections import defaultdict import heapq hour=defaultdict(int) order=defaultdict(list) cnt=defaultdict(int) n=int(input()) for i in range(1,n+1): m=list(map(int,input().split())) hour[i]=m[0] if m[1]==-1: continue for j in m[1:-1]: order[j].append(i) # i이전에 j가 성행한다 cnt[i]+=1 q=[] ans=[0]*(n+1) for i in range(1,n+1): if cnt[i]==0: q.append(i) ans[i]=hour[i] while q: x=q.pop() for y in ord..
위상정렬 + 우선순위큐 문제번호가 작은 것 부터 풀어야된다 from collections import defaultdict import heapq height=defaultdict(list) cnt=defaultdict(int) q=[] n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: q.append(i) result=[] while q: x=heapq.heappop(q) result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]..
www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 �� www.acmicpc.net 다익스트라 유형 import sys import collections import heapq t=int(sys.stdin.readline()) for kk in range(t): n,d,c=map(int,sys.stdin.readline().split()) graph=collections.defaultdict(list) for i in range(d): a,b,s=map(int,sys.stdin.readlin..
import sys import collections import heapq V,E=map(int,sys.stdin.readline().split()) K=int(sys.stdin.readline()) graph=collections.defaultdict(list) for i in range(E): u,v,w=map(int,sys.stdin.readline().split()) graph[u].append((v,w)) dist=collections.defaultdict(int) q=[(0,K)] while q: time,node=heapq.heappop(q) if node not in dist: dist[node]=time for v,w in graph[node]: alt=time+w heapq.heapp..
문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1
문제 수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로..
1. javascript function solution(expression) { const prior=[['+','-','*'],['+','*','-'],['*','-','+'],['*','+','-'], ['-','+','*'],['-','*','+']]; // 순열로 돌려도 되고 최대 6가지 const nums=[]; const opers=[]; let num=''; expression.split("").map((x)=>{ if(x>='0' && x
dp인건 알겠는데 어디서 계산이 틀린 부분이 있는지 한참을 안되다가 다시 해보니까 3분만에 풀림 이것이 인생 1. 거스름돈 1,2,5원 중 1원을 낼 수 있는 것 다 더해주고 그다음 2원으로 계산되는 것 다 내준다. 그 다음 5원 순으로 더한다 배열 말고 그냥 dict을 사용했고 from collections import defaultdict def solution(n, money): dp=defaultdict(int) dp[0]=1 for m in money: for i in range(m,n+1): dp[i]+=dp[i-m]%1000000007 return dp[n] 2. 자바스크립트 function solution(n, money) { var answer = 0; let dp=new Array(n+..
1. python 풀이 def solution(s): answer = [] temp=[] for i in s[2:-2].split('},{'): temp.append(i.split(',')) temp.sort(key=len) for t in temp: for item in t: if int(item) not in answer: answer.append(int(item)) return answer 2. javascript 풀이 function solution(s) { var answer = []; s=s.split("").map(ch=>{ if(ch==="{" || ch==="}"){ return ""; } return ch; }).join("").split(","); const dict={}; for(l..