자료구조

1715 백준 파이썬

힙 그자체인 문제 import heapq n=int(input()) 결과=0 힙=[] for _ in range(n): heapq.heappush(힙, int(input())) while len(힙)!=1: 임시=heapq.heappop(힙) if 힙: 임시=임시+heapq.heappop(힙) 결과+=임시 heapq.heappush(힙,임시) print(결과)

23254 백준 파이썬

괜히 힙 두개쓸려다가 개같이 멸망했던 문제 남은 숫자를 새 단위로 힙에 넣는걸 생각하지 못해서 굉장히 고민했다. 이번엔 특별히 한글 코드로 작성했다. 사랑해요 연예가중계 import heapq n,m=map(int,input().split()) # 24*n시간 후 시작 time=24*n # m과목 a=list(map(int,input().split())) b=list(map(int,input().split())) 결과=0 힙=[] for x in range(m): heapq.heappush(힙, [-b[x],a[x]]) while 힙: 힙에서뽑은거=heapq.heappop(힙) 단위,점수=-힙에서뽑은거[0],힙에서뽑은거[1] while 단위+점수0: 점수+=단위 time-=1 else: break if ..

12731 백준 파이썬

각각 역에 대한 출발시간을 heap에 저장한다. 각 역은 save라는 heap을 가지며, 해당 heap보다 출발시간의 heap이 큰 경우, count가 커지지 않는다. 해당 heap의 출발시간이 save보다 작은경우, count는 커진다. heap에서 꺼낸 시간의 도착시간에 회차시간을 더한뒤에 상대편 역의 save에 push 한다. 코드가 매우 더럽다. 내일중으로 정리해서 업데이트 할 예정 import heapq from collections import deque from tracemalloc import start def function_a(a,acount,asave,bsave): now_a=heapq.heappop(a) start_hour,start_minutes=now_a[0].split(":")..

3078 백준 파이썬

윈도우를 덱으로 구성해주었다. 윈도우 크기가 k+1미만이면 윈도우에 append하고, 이름길이 배열의 갯수를 더해준다. 윈도우 크기가 k+1(k등 이상 차이이므로)나게 되면 popleft하여, 해당 값의 이름 길이 배열의 갯수에서 빼준다. 마지막에는 window에는 k+1이하의 길이를 가진 값들이 남게 되는데 이 값들을 동일하게 큐느낌으로 처리해주었다. import sys input=sys.stdin.readline from collections import deque n,k=map(int,input().split()) count=[0 for x in range(21)] name=[] window=deque() ans=0 for x in range(n): name.append([x+1,len(input(..

17503 백준 파이썬

맥주파뤼~~ heap은 알콜이 낮은 순서로,. answer에는 prefer가 낮은대로 각각 두개의 heap을 사용했다. 입력된 값을 바로 heap에 넣어서 알콜도수가 낮은순대로 저장하고, 이들의 수가 n에 도달했을때, 만족도를 넘기지 못하면 answer의 값 중 가장 만족도가 낮은 것을 뺀다. 이때 만약 알콜이 가장 높은 것이면 두번째로 알콜값이 높은 값을 가장 높은 값으로 바꿔준다. 이걸 heap이 존재할때까지 반복하고, 없으면 -1를 출력하게 했다. 문제가 있었던 점은 second_alchol을 사용하지 않고, answer에서 반복문을 찾아서 maxalchol을 찾으려고 했더니 시간초과가 났다는 점이다. 시간초과가 난 코드 import heapq n,m,k=map(int,input().split())..

13335 백준 파이썬

처음에는 시간을 계산해서 구해주려고 했다. 실패한 코드 from collections import deque n,w,l=map(int,input().split()) truck=list(map(int,input().split())) d=deque() s=0 time=0 for x in truck: if x+sl: y=d.popleft() s-=y if d: time+=1 s+=x d.append(x) if d: time+=w while d: d.popleft() time+=1 print(time) 이 경우 5 2 2 1 1 1 1 1과 같은 경우를 생각하지 못했다. 정답은 무지성 덱 시뮬레이션 이다. 덱으로 다리를 만들어서 직접 트럭을 이동시켜주었다. from collections import deque ..

3107 백준 파이썬

s=input() l=[] ret=[] start=0 for x in range(len(s)): if s[x]==':': l.append(s[start:x]) start=x+1 l.append(s[start:]) for x in l: if len(x)==4: ret.append(x) elif len(x)==3: ret.append('0'+x) elif len(x)==2: ret.append('00'+x) elif len(x)==1: ret.append('000'+x) else: ret.append('') tmp=[] for x in range(len(ret)-1): if ret[x]=='': t=9 if ret[x+1]=="": t=10 for i in range(t-len(ret)): tmp.appen..

1254 백준 파이썬

간단하게 해결했다. 일단 팰린드롬을 체크해야하는데, 문제에서 붙이는 문자열은 무조건 뒤에 붙으므로 맨 뒤의 문자열과 동일한 문자를 갖는 인덱스들로 부터 팰린드롬 체크를 시작한다. 그리고, while s[i]==s[j]로 하나씩 인덱스를 좁히며 (i+=1, j-=1) i==j인 경우나, 예시 ) abcba i>j인 경우, 예시) abaaba 팰린드롬 문자열이므로 시작문자열의 인덱스+총 문자열의 길이를 출력해주었다. s=input() i=0 cnt=0 length=len(s) for x in range(length): j=length-1 ck=0 if s[x]==s[j]: i=x while s[i]==s[j] and i=j: print(x+length) exit()