Henry's Algorithm

Codility Lesson 6의 마지막 문제다.

Triangle 이라는 문젠데, 배열 안에 3개의 수가 아래의 조건을 만족하는 지의 여부를 묻는 문제다.

A[i] + A[j] > A[k]

A[j] + A[k] > A[i]

A[i] + A[k] > A[j]

(단, 0< i,j,k < N)

최대한 for 문을 안쓰고 싶은데, 어떻게 해야할까..

for 문 3개 쓰니깐, 마지막 3문제는 Timeout Error가 발생했다.ㅜㅜ

시간 복잡도: O(N**3) --> 81%의 정답률

# 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
    
    A = sorted(A)
    
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            for k in range(j+1,len(A)):
                if A[i] + A[j] <= A[k]:
                    break
                else:
                    if is_triangular(A[i],A[j],A[k]) == 1:
                        return 1
            
    return 0
    pass


def is_triangular(a,b,c):
    if a+b > c and a+c > b and b+c > a:
        return 1
    else:
        return 0

크기에 따라서 오름차순으로 정렬하고,

for문 하나로 문제를 푸니 풀렸다!!

ex) 1,2,5,8,10,20 로 정렬을 하면,

a < b < c이렇게 정렬이 될때,

일단 a + c > b 는 당연한 사실 c가 b 보다 크기 때문에.

그리고 c + b > a도 당연한 사실 c,b가 a보다 크기 때문에,

그러므로 a + b > c 인지만 확인하면 됨.

시간 복잡도: O(N*log(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
    
    A = sorted(A)
    
    for i in range(len(A)-2):
        if A[i] + A[i+1] > A[i+2]:
            return 1
    
    return 0
    pass

관련 유튜브 강의도 있습니다~~

https://www.youtube.com/watch?v=IxLlq9RGFI8

저의 강의입니다ㅋㅋㅋ

열심히 풀려고 하였으나, 반복문 2번 돌리는 거 외에는 생각이 잘 안났다.ㅜㅜ

결국 정답을 보고 이해하였지만, 앞으로도 열심히 해야겠다.

내 코드: 시간 복잡도: O(N ** 2) --> 53%의 정답률

# 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
    
    count = 0
    
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            tmp = i+A[i] 
            tmp2 = j-A[j]
            if tmp2 <= tmp:
                count += 1
                
    return count
                
            
    
    pass

구글링한 코드: 시간 복잡도: O(N*log(N)) or 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
    
    arr = []
    
    for i,v in enumerate(A):
        arr.append((i+v,1))
        arr.append((i-v,-1))
        
    arr.sort()
    
    
    intersect = 0
    intervals = 0
    
    for i,v in enumerate(arr):
        if v[1] == 1:
            intervals -= 1
        if v[1] == -1:
            intersect += intervals
            intervals += 1
    
    if intersect > 10000000:
        return -1
    
    return intersect
    pass

ㅜㅜ 열심히 풀려고 해보았지만, 생각보다 다른 접근 방법이 생각이 나지 않아 골머리를 앓았다.

코드는 다음의 블로그를 참고했다.

https://m.blog.naver.com/PostView.nhn?blogId=evanecen&logNo=221359303451&proxyReferer=https:%2F%2Fwww.google.com%2F

다들 화이팅

코로나 19 다함께 이겨냅시다!

관련 유튜브 강의도 있습니다~~~

https://www.youtube.com/watch?v=Ell5C1yoBRQ

저의 강의입니다ㅋㅋㅋ

시간 복잡도: O(N * log(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
    
    A = sorted(A, reverse=True)
    
    if A[0]*A[1]*A[2] > A[0]*A[-1]*A[-2]:
        return A[0]*A[1]*A[2]
    else:
        return A[0]*A[-1]*A[-2]
    
    pass

관련 유튜브 강의도 있습니다~~!!

https://www.youtube.com/watch?v=gFpzBTytLPY

저의 강의입니다ㅋㅋㅋ

# 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) == 0:
        return 0
    
    B = set(A)
    
    return len(B)
    
    pass

# 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
    
    east_car_num = 1
    
    passing_car_num = 0
    
    # 최초 동쪽으로 가는 차 위치
    try:
    # 동쪽으로 가는 차가 없으면 에러 발생하여 passing_car가 없으므로 return 0
        east_car = A.index(0)
    except:
        return 0
        
    for i in range(east_car+1,len(A)):
        if A[i] == 1:
            passing_car_num += east_car_num
            
            if passing_car_num > 1000000000:
                return -1
        else:
            east_car_num += 1
            
            
    return passing_car_num
    
    
    pass

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

핵심은 이렇다.

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

시간 복잡도: O(N + M) --> 100%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(S, P, Q):
    # write your code in Python 3.6
    
    # step 1 - input array S,P,Q
    # already succeed
    
    # step 2 - get range from array P,Q
    M = len(P)
    
    return_arr = []
    
    # step 3 - do the job(for senetence)
    for i in range(M):
        arr = S[P[i]:Q[i]+1]
        try:
            arr.index('A')
            return_arr.append(1)
        except:
            try:
                arr.index('C')
                return_arr.append(2)
            except:
                try:
                    arr.index('G')
                    return_arr.append(3)
                except:
                    return_arr.append(4)
                    
    return return_arr
        
    pass

시간 복잡도: O(B-A) --> 50%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B, K):
    # write your code in Python 3.6
    
    # step 1 - input A,B,K
    # already succeed
    
    # step 2 - do the for sentence
    return_value = 0
    
    for i in range(A,B+1):
        if i % K == 0:
            return_value += 1
            
    return return_value
    pass

시간 복잡도: O(1) --> 100%의 정답률

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B, K):
    # write your code in Python 3.6
    
    start_num = A/K
    end_num = int(B/K)
    
    if start_num%1 != 0:
        start_num = int(start_num) + 1
    else:
        start_num = int(start_num)
    
        
    return end_num - (start_num-1)
    pass