개발새발

[문제] 배열에서 3개의 수를 뽑아 어떤 2개의 수의 합이 나머지 1개의 수보다 큰 조합이 있는지 찾는 문제 Triangle coding task - Learn to Code - Codility Determine whether a triangle can be built from a given set of edges. app.codility.com [코드] 시간복잡도 : O(N*log(N)) 정렬 후에는 A[idx]+A[idx+2] > A[idx+1], A[idx+1]+A[idx+2] > A[idx] 가 당연한 것을 활용 예) [1, 1, 1] -> 1+1>1 / [1, 2, 3] -> 1+3 > 2, 2+3>1 def solution(A): # write your code in Python 3.6 if(..

[문제] 주어진 선의 좌표 중 서로 겹치지 않는 좌표들의 조합의 최대수를 찾는 문제 MaxNonoverlappingSegments coding task - Learn to Code - Codility Find a maximal set of non-overlapping segments. app.codility.com [코드] 시간복잡도 : O(N) def solution(A, B): # write your code in Python 3.6 if not A: return 0 standard = B[0] answer=1 for idx, a in enumerate(A) : if idx==0 : continue else : if a > standard : answer=answer+1 standard=B[idx] ..

[문제] 주어진 조건에 맞게 주차 요금을 계산하는 문제 - 입장료 : 2 - 첫 1시간 : 3 - 이후 시간 : 4 [코드] def solution(E, L): # write your code in Python 3.6 tempE = E.split(':') tempL = L.split(':') answer = 5 startH = int(tempE[0]) * 60 startM = int(tempE[1]) endH = int(tempL[0]) *60 endM = int(tempL[1]) start = startH + startM end = endH + endM count = end - start div = int(count/60) left = count%60 if div >= 1 : answer = answe..

[문제] 원 형태로 놓인 N개의 초콜렛을 M칸씩 이동하며 먹었을 때 먹을 수 있는 초콜렛의 수를 세는 문제 [코드] 시간복잡도 : O(N+M) (성능 테스트 Fail) def solution(N, M): # write your code in Python 3.6 answer=1 check = [0] * N check[0]=1 current=0 while True : current = current + M if check[current%N] == 1 : break; else : check[current%N] = 1 answer = answer+1 return answer 시간복잡도 : O(log(N+M)) (성능 테스트 Pass) 최대 공약수 활용 import math def solution(N, M): #..

[문제] 배열 중 3개의 수의 곱이 가장 큰 값을 리턴하는 문제 MaxProductOfThree coding task - Learn to Code - Codility Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R). app.codility.com [코드] 시간복잡도 : O(N*log(N)) 배열 소팅 후(desc) 가장 큰 값 3개의 곱과 가장 큰 값 1개와 가장 작은 값 2개의 곱을 비교 def solution(A): # write your code in Python 3.6 A.sort(reverse=True) lenth = len(A) answer = max(A[0]*A[1]*A[2], A[0]*A[lenth-1]*A[lenth-2]) return an..

[문제] 절대값 기준으로 배열 내 unique한 숫자의 수를 세는 문제 AbsDistinct coding task - Learn to Code - Codility Compute number of distinct absolute values of sorted array elements. app.codility.com [코드] 시간복잡도 : O(N) def solution(A): # write your code in Python 3.6 answer = set() for idx, value in enumerate(A) : if value < 0 : A[idx] = A[idx] * -1 answer.add(A[idx]) return len(answer)

[문제] 주어진 수의 모든 약수의 개수를 구하는 문제 CountFactors coding task - Learn to Code - Codility Count factors of given number n. app.codility.com [코드] N이 큰 값으로 주어지기 때문에 시간복잡도가 O(N)라면 timeout이 발생한다. 제곱근의 약수의 개수를 구하여 해당 값을 활용한다. import math def solution(N): # write your code in Python 3.6 sqrt_value = math.sqrt(N) answer= 0 i = 1 while i < sqrt_value : if N%i == 0: answer = answer + 1 i = i+1 answer = answer*2 ..

[문제] 배열 내 각 날짜 별 물건 가격이 주어지고, 과거에 산 물건을 팔았을 때 최대 이윤을 찾는 문제 MaxProfit coding task - Learn to Code - Codility Given a log of stock prices compute the maximum possible earning. app.codility.com [코드] 최소 가격과 최대 이윤을 저장함 def solution(A): # write your code in Python 3.6 if len(A) >= 1 : min_price = min(A[0], A[1]) answer = A[1] - A[0] for i in A[2:len(A)] : min_price = min(min_price, i) answer = max(ans..

[문제] 전체 배열의 중에서 절반 이상 반복되어 나타나는 숫자가 있는지 찾고 있다면 그 숫자의 index를 리턴하는 문제 Dominator coding task - Learn to Code - Codility Find an index of an array such that its value occurs at more than half of indices in the array. app.codility.com [코드] Dictionary를 이용해 값 별로 등장 횟수를 카운팅 함 시간복잡도 : O(N*log(N)) or O(N) def solution(A): # write your code in Python 3.6 max = 0 max_val = 0 dict= {} for i in A : if dict.ge..

[문제] 서로 움직이는 방향이 다른 물고기들이 마주쳤을 때 물고기 크기에 따라 작은 물고기는 죽고 큰 물고기만 살아남을 때 전체적으로 살아남는 물고기 수를 세는 문제 Fish coding task - Learn to Code - Codility N voracious fish are moving along a river. Calculate how many fish are alive. app.codility.com [코드] Stack에 downstream으로 움직이는 물고기를 담고 크기를 비교하여 살아 남는 물고기 수를 카운팅 함 시간복잡도 : O(N) def solution(A, B): # write your code in Python 3.6 fish = [] answer = 0 for idx, f in ..