CS

생각보다 까다로웠던 문제 import heapq n=int(input()) m=[] for _ in range(n): m.extend(list(map(int,input().split()))) reverse_sign = lambda x: x*-1 m=list(map(reverse_sign,m)) heapq.heapify(m) for _ in range(n-1): heapq.heappop(m) print(-heapq.heappop(m)) 이렇게 모든 수를 힙에 집어넣고, 출력했더니 메모리 초과가 났다. 이유는 int가 32비트이기 때문이다. 32*1500*1500/1000000 = 72MB이기때문이다. 그래서 힙을 n개로 유지했다. import heapq n=int(input()) heap=[] for _ ..

꽤나 중요한 것을 배웠던 문제 아래는 시간초과 났던 코드이다. n=int(input()) l=list(map(int,input().split())) result=[0 for x in range(n)] for x in range(len(l)): stack=l[:x+1] now=stack.pop() t=0 cnt=0 while tl[x]: result[x]=stack[-1][0]+1 break else: stack.pop() stack.append([x,l[x]]) result=map(str,result) print(" ".join(result)) 코드 구조와 별개로 시간복잡도가 달라질 수 있다는 것을 배웠다. 조금더 파봐야 하겠지만 꽤나 흥미롭다.

처음에는 dfs로 해결하려 했지만, 시간 초과에 부딪혔다. 답은 우선순위 큐였다. 하나만 쓸려다가 계속 막혔는데 두개를 써보니 해결됐다. 우선순위 큐에서 꺼내면서 그 값의 end값을 q안에 push한다. 그리고 end값과 q[0]을 비교하고, 만족했을 때 그값을 빼내면 된다. 비교했을때 만족하지 못해도 그냥 q에 넣는다. 마지막엔 q에 남아있는 값의 수를 출력해주면 된다. #https://www.acmicpc.net/problem/1374 import sys import heapq input=sys.stdin.readline n=int(input()) lecture=[] q=[] for _ in range(n): l=list(map(int,input().split())) heapq.heappush(lec..

조건 정리 1. 이름이 중복되면 더이상 값을 안받음 2. 겹치는 시간대의 수가 가장 많은 장소를 골라냄 3. 많은 경우 사전순으로 배열 4. 그 중에서 가장 빠른 시간대를 골라냄 풀이 메모리 제한이 512MB인데, 시간대 제한인 50000으로 계산하면 총 제출수 10(각각 다른 장소 일 수 있으므로)*50000*4(int)가 되겠다. 총 2MB이므로 매우 널널하게 잡아 줄 수 있다. 그래서 장소마다 딕셔너리로 50000따리 리스트를 할당했다. 그리고 제출 받을때, 시작점과 끝점까지 반복시키며 시간대를 증가시켜준다. 가장 큰 숫자가 찍힌 부분이 겹치는 부분이다. 그리고 동시에 겹치는 부분이 가장 큰 장소를 maxplace에 저장했다. maxplace의 숫자가 크다면, maxpace를 비워주고, 그것만 추가..

stack을 사용해 해결했다. 사실 zip부분은 큐를 쓰면 좀 더 빠를 것 같지만... 그냥 stack으로 해봤다. 문자와 숫자를 동시에 받아서 처리하는데 예외상황이 나와서 처리하는데 애먹었다. #https://www.acmicpc.net/problem/23300 def doforward(now): if forward: backward.append(now) now=forward.pop() return now def dobackward(now): if backward: forward.append(now) now=backward.pop() return now def connect(where,now): if now=='first': now=where else: backward.append(now) now=wh..

힙을 사용했다. 근데 동시에 가져올때 상민이 것(B)가 먼저 나와야하므로 임시 배열에 저장한 다음, B인 것 부터 힙에 넣어줬다. import heapq heap=[] tmpl=[] B=[] R=[] a,b,n=map(int,input().split()) for _ in range(n): t,c,m=map(str,input().split()) t=int(t) m=int(m) time=t first=1 for _ in range(m): if not first: if c=='B': time=time+a elif c=='R': time=time+b tmpl.append([time,c]) first=0 for x in tmpl: if x[1]=='B': heapq.heappush(heap,x) for x in ..

오랜만의 DFS 무엇을 리스트와 딕셔너리에 저장할지 고민하는데 시간이 많이 걸렸다. 중요한 건 " 환승 "이다. 따라서 환승 못하는 역들에 대해서는 굳이 dfs연산을 할 필요가 없다. 환승 할 수 있는 것들은 h[x]의 길이가 2보다 크다. 이것들에 대해서만 dfs연산을 진행했다. def dfs(start, dest,cnt): havetogo=[] for x in route[start]: if x==dest: return cnt if len(h[x])==1 and x not in vis: #환승 못하는 것들 vis.append(x) else: if x not in vis: vis.append(x) havetogo.append(x) for x in havetogo: return dfs(x, dest,cnt..

처음에는 슬라이싱과 집합을 생각하지 못해서 시간초과가 났다. import sys sys.stdin.readline s=input() chk={} res=[] for x in range(len(s)): l=[] for i in range(len(s)-x): l.append(s[x+i]) if chk.get(''.join(t for t in l))!=1: res.append(''.join(t for t in l)) chk[''.join(t for t in l)]=1 print(len(res)) 집합을 쓰면 딕셔너리를 안써도 된다. import sys sys.stdin.readline s=input() res=set() for x in range(len(s)): for y in range(x, len(s)):..

실버 3에 40분을 태워? 자료구조는 너무 어렵다. 배워야 할게 산더미다. 스택과 딕셔너리를 통해 해결했다. 딕셔너리를 통해 스택에 그 값이 있는지 체크하고, pop을통해 출력한다. 열받는점은 k개 출력할려고 했는데 k보다 작은 값을 출력할 때의 테스트 케이스가 들어가있어서 런타임 에러가 뜬다는 것이다. #https://www.acmicpc.net/problem/13414 import sys input=sys.stdin.readline d=[] stack=[] check={} k,l=map(int, input().split()) now=0 for _ in range(l): n=input().rstrip() d.append(n) while d: tmp=d.pop() if check.get(tmp)!=1: ..

자료구조 종합세트 stack, heap, deque까지 쓸려고 했으나 deque은 못썼다. 첫 생각에 덱을 사용해서 앞에서 빼서 뒤로 넣는 순환을 만들려고 했는데 반복문으로 쉽지 않았다. 그래서 넘기는 배열을 따로 선언해주고 stack을 넘겨 비교를 통해 해결했다. 시간을 너무 많이 썼다. 아직 많이 부족하다. #우선 순위 숫자가 높은게 먼저 적재, 낮은 건 나중에 적재 #우선순위가 같으면 무게 무거운 것 먼저 적재. import heapq import sys limit_number = 15000 sys.setrecursionlimit(limit_number) def cal(stack,l,std): global cost next=[] for x in l: if x[0]==std: priority[std]..