정렬하면 nlogn이 되고 이 방식은 O(n)으로 풀린다 def solution(A): # write your code in Python 3.6 n=1000001 check=[False]*n for e in A: if e>=1: check[e-1]=True for i in range(n): if check[i]==False: return i+1
계속해서 현재의 최대값이 있다면 기록해둔다. 만약 n+1이 나오면 가장 큰 값을 바꿔주고 그것보다 작은 수는 업데이트해준다 최소한의 값이 되지 않은 수들을 다시 가장 큰 값 변수에 기록된 걸로 바꿔준다 # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(N, A): res=[0]*N biggest,cur=0,0 for e in A: if e==N+1: biggest=cur else: if biggest>res[e-1]: res[e-1]=biggest res[e-1]+=1 if res[e-1]>cur: cur=res[e-1] for i in range(N): if res[i]
문자열로 슬라이싱해서 sum으로 더해서 구하면 O(n^2)이 된다 또 한쪽의 길이가 0이 되도록 자르면 안되고 무조건 1개 이상의 원소는 포함해야 된다 하나는 하나만 포함하고 하나씩 수를 더해주는 반면 긴 부분에서는 앞에서부터 하나씩 빼서 차이를 구해주면 된다 timecomplexity: O(n) def solution(A): # write your code in Python 3.6 first=A[0] second=sum(A[1:]) res=abs(first-second) for i in range(1,len(A)-1): first+=A[i] second-=A[i] res=min(res,abs(first-second)) return res
Question: https://codility.com/demo/take-sample-test/binary_gap # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(N): cur,max_gap=0,0 for i,e in enumerate(str(bin(N)[2:])): if e=='1': max_gap=max(max_gap,cur) cur=0 else: cur+=1 return max_gap
한 가지 없는 원소를 찾는 것 (1부터 시작해서) 빈배열일 경우, 마지막이나 첫 원소가 없을 경우, 홀수개의 원소, 짝수개의 원소일 경우를 모두 체크해주는 경우의 수를 공부할 수 있었다 def solution(A): if not A: return 1 # 빈 배열은 당연 1을 리턴 A.sort() # 정렬해서 중간에 없는 수를 찾아보자 num=1 for i,e in enumerate(A): if num!=e: return num else: num+=1 return num # 마지막 원소가 없는 경우 다른 사람 풀이인데 이전에 bitwise로 계산하는 문제같다 def solution(A): length = len(A) xor_sum = 0 for index in range(0, length): xor_sum..
1 ~ x까지 나오면 현재의 인덱스(초)를 리턴해준다 O(n) # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") import collections def solution(X, A): # write your code in Python 3.6 dict=collections.defaultdict(int) for i,e in enumerate(A): dict[e]=1 if len(dict)==X: return i return -1
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최소 경로를 bfs로 찾는 법 from collections import deque def bfs(): dq=deque() dq.append((0,0)) vis[0][0]=1 cnt=1 while dq: x,y=dq.popleft() if x==n-1 and y==m-1: return vis[x][y] for k in range(4): xx,yy=x+dx[k],y+dy[k] if xx=n or yy=m: continue if vis[xx][y..
홀수번 등장하는 숫자를 반환하는 대표 문제다 def solution(A): result=0 for num in A: result^=num return result
height: 현재 번호 작업을 하기 위한 우선순위 작업들을 담고 있다 cost: 현재 작업의 비용(시간) 모든 작업을 돌면서 현재 번호를 작업하기 위해 먼저 해야할 작업들의 비용의 최대값(여러 작업을 동시에 할 수 있다는 조건이 있다)에 현재 작업의 시간을 더한 것이 현재 번호를 작업하는 걸리는 시간이다 from collections import defaultdict import heapq height=defaultdict(list) cost=defaultdict(int) n=int(input()) for i in range(1,n+1): c=list(map(int,input().split())) cost[i]=c[0] if c[1]==0: continue for j in c[2:]: height[i]..
from collections import defaultdict from collections import deque height=defaultdict(list) cnt=defaultdict(int) dq=deque() 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: dq.append(i) result=[] while dq: x=dq.popleft() result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]==0: dq.appe..