파이썬

바보같이 코드 짜서 괜히 엄청 해맸던 문제 일단 한 점의 색깔을 임의로 지정하고, 인접한 점들을 모두 변경해줘야 하기떄문에 dfs보다는 bfs가 나을 것이다. 그래서 코드를 짰는데, 바보처럼 bfs(1)을 실행시켰다. 이러면 1이 독단적으로 떨어져 있는 경우, 코드가 실행이 안된다. 괜히 keyError가 나서 도대체 뭐지 싶었다. 정답코드 #https://www.acmicpc.net/problem/13265 import sys from collections import deque input=sys.stdin.readline def bfs(start): global impossible q=deque() if vis[start]=="B": origin="B" op="W" else: origin="W" op..

상당히 어려웠다. 합을 기록해서 뺀 것과 비교한다는 것을 떠올리기 너무 힘들었다. a+b+c=d라는 식에서 a+b=d-c를 유도해서 풀어야 했다. 그러면 수를 3개만 골라도 되기때문에 O(N^3)으로 풀 수 있다. #https://www.acmicpc.net/problem/2295 n = int(input()) u = set() ans=[] for i in range(n): u.add(int(input())) sums = set() for i in u: for j in u: sums.add(i + j) for i in u: for j in u: if (i - j) in sums: ans.append(i) ans.sort() print(ans[-1])

복잡하지만 꼼꼼히 잘 작성해 주면 됐던 문제 마지막에 good을 추가로 출력해주면서, 반례를 잡아주었다. import heapq from collections import deque n=int(input()) line=deque() heap=[] stack=[] #대기줄 for _ in range(n): l=list(map(str,input().split())) for x in l: a,b=x.split('-') b=int(b) heapq.heappush(heap,[a,b]) line.append([a,b]) while heap: target=heapq.heappop(heap) while line: x=line.popleft() if x!=target: if stack: y=stack.pop() if y..

사과와 뱀은 matrix와 visited(덱)에 기록하고, 시간은 힙에 넣어서 보관했다. 방향 계산을 떠올리기 힘들었던 문제 from collections import deque import heapq def change(d, c): if c == "L": d = (d - 1) % 4 else: d = (d + 1) % 4 return d def start(): direction = 1 time = 1 y, x = 0, 0 visited = deque([[y, x]]) matrix[y][x] = 2 if times: ftime=heapq.heappop(times) else: ftime=[] while True: y, x = y + dy[direction], x + dx[direction] if 0

뒤에 들어온 문장부터 확인해서 문자열 리스트에 추가해부고, 겹치는게 하나도 없다면 c만큼 출력하고, 겹치는게 있을때마다 c값을 하나씩 깎아내면 된다. 중복 유무는 딕셔너리로 확인해주었다. r,c=map(int,input().split()) table=[] for _ in range(r): l=list(input()) table.append(l) cnt=r-1 strlist=['' for _ in range(c)] while table: li=table.pop() ch={} k=0 for x in range(c): if ch.get(strlist[x]+li[x]) is None: strlist[x]=strlist[x]+li[x] ch[strlist[x]]=1 else: strlist[x]=strlist[x..

생각보다 까다로웠던 문제 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..

처음에는 슬라이싱과 집합을 생각하지 못해서 시간초과가 났다. 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: ..