반응형
20%의 정답률 코드ㅠㅠ
# 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
# step 1 - input array A
# already succeed
tmp = sum(A[0:2])/len(A[0:2])
# step 2 - get the avaerage value in for loop
A_length = len(A)
for P in range(A_length):
for Q in range(P+1,A_length-1):
arr_ = A[P:Q+1]
arr_sum = sum(arr_)
arr_len = len(arr_)
if tmp >= arr_sum/arr_len:
tmp = arr_sum/arr_len
return_value = P
return return_value
pass
slice가 몇개까지 쪼개질 지 그 길이를 먼저 구하고 그만큼만 돌리려고 하는 코드는 좋은 접근이었다.
# 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
# step 1 - input array A
# already succeed
# step 2 - get a length of slice
slice_len = len(A)-1
length = len(A)
arr = []
for i in range(2,slice_len):
for j in range(slice_len-i+1):
arr.append(sum(A[j:j+i])/len(A[j:j+i]))
print(j,"###",sum(A[j:j+i])/len(A[j:j+i]))
return min(arr)
한개씩 더해가면서 최솟값을 구하려고 하는 접근도 정답률은 좋지 못했지만, 나름 괜찮은 발상이었다.
# 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
if len(A) == 3:
return 0
# step 1 - input array A
# already succeed
length = len(A)-1
X = A[:length-1]
Y = A[1:length]
C = [x+y for x,y in zip(X,Y)]
tmp = min(C)/2
print(C.index(min(C)))
return_value_index = C.index(min(C))
for i in range(2,length):
print(i)
Y = A[i:length]
print(Y)
C = [x+y for x,y in zip(C[:length-i],Y)]
print(C)
if tmp >= min(C)/i+1:
tmp = min(C)/i+1
return_value_index = C.index(min(C))
return return_value_index
다양한 시도 끝에 결국 구글의 힘을 빌렸다.ㅠㅠ
잘 설명해주신 링크가 있어서 미리 출처를 밝힌다.
https://cheolhojung.github.io/posts/algorithm/Codility-MinAvgTwoSlice.html
[Codility] MinAvgTwoSlice 문제 풀이 | jcheolho
배열의 모든 조합(P부터 Q까지, 0 <= P < Q)의 평균값에 대해서 최소 평균값을 갖는 P를 찾는 문제이다. 첫번째 풀이 O(N^2) 일단 무식한 방법으로 풀어봤는데, 당연히 time out에 걸릴 줄 알았고, 코드도 딱히 설명할 필요가 없으므로 패스하자. 두번째 풀이 구간 합에 분류되어 있길래 응용할 수 있는 방법을 생각해봤는데 도저히 생각나질 않는다. 결국 이번 문제도 구글의 힘을 빌렸다. 참고 . 이 포스팅을 작성하신 분이 가장 이해하기 쉽게
cheolhojung.github.io
핵심은 이렇다.
4개의 원소의 평균은 2개씩 나누어서, 각 (2개의 평균)의 최솟값보다 크다고 한다. 그래서 최솟값이 있는 위치(인덱스)를 구하면 되는 문제였다. 열심히 풀어보았는데 생각보다 정확도가 잘 안되서 화가난다.!!
아래는 시간복잡도 O(N)의 100% 정답코드다
# 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[0:2])/2
min_index = 0
for i in range(len(A)):
try:
if min_value > (A[1+i] + A[i])/2:
min_value = (A[1+i]+A[i])/2
min_index = i
if min_value > (A[2+i] + A[1+i] + A[i])/3:
min_value = (A[2+i] + A[1+i] + A[i])/3
min_index = i
except:
break
return min_index
pass
반응형
'Codility' 카테고리의 다른 글
| Codility - Distinct (0) | 2020.04.23 |
|---|---|
| Codility - PassingCars (0) | 2020.04.20 |
| Codility - GenomicRangeQuery (0) | 2020.04.19 |
| Codility - CountDiv (0) | 2020.04.18 |
| Codility - PermCheck (0) | 2020.04.18 |
