수학적인 풀이가 대부분이라 수학적으로 풀었는데 그렇게 풀기 위한게 맞는 건지 모르겠다 알고리즘 능력 기르려고 대표 문제 풀때는 수학적인 문제 나오면 좀 싫다 ㅠㅠ 배열이 2개인 경우와 3개인 경우로 나눠서 풀면 되는데 4개인 경우에는 배열 2개인 경우보다 절대로 작을 수 없기 때문이다. (수학 공식) # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A): # write your code in Python 3.6 min_value=sum(A[:2])/2 ans=0 # 3개인 배열을 위해서 인덱스 제한 for i in range(1,len(A)-2): # 원소 2개인 배열 ..
음수 경우를 생각하면서 풀어야 되는 문제 1. 가장 작은 수들이 음수인 경우 가장 작은 음수 2개 (절대값은 크다) * 가장 큰 원소를 곱할 경우 가장 큰 원소가 나올 수 있다. 가장 큰 원소도 음수인 경우는 자연스럽게 작은 수가 된다 2. 한 경우는 모든 것이 양수이고 세 개 곱한 것이 가장 큰 수인 경우이다 def solution(A): # write your code in Python 3.6 A.sort(); a=A[-1]*A[-2]*A[-3] b=A[0]*A[1]*A[-1] if a>b: return a else: return b
from collections import defaultdict def solution(A): dict=defaultdict(int) for e in A: dict[e]=1 return len(dict)
정렬하면 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
홀수번 등장하는 숫자를 반환하는 대표 문제다 def solution(A): result=0 for num in A: result^=num return result