본문 바로가기

카테고리 없음

코딜리티 lesson3 시간복잡도(Time Complexity) - FrogJmp, PermMissinElem, TapeEquilibrium

FrogJmp

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

def solution(X, Y, D):
    ans = (Y-X)//D
    if (Y-X)%D == 0:
        return ans
    else:
        return ans + 1

 

PermMissinElem

[최초풀이]

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

def solution(A):
    A = sorted(A)
    while A:
        try:
            a = A.pop()
            b = A.pop()
        except:
            break
        if a - b > 1:
            return a-1

 

[다른풀이]

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

def solution(A):
    sumN = int(((len(A)+2) * (len(A)+1))/2)
    return sumN - sum(A)

 

TapeEquilibrium

[최초풀이]

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

def solution(A):
    diff = []
    for P in range(1, len(A)):
        sum1 = sum(A[:P])
        sum2 = sum(A[P:])
        diff.append(abs(sum1-sum2))
    return min(diff)

[다른풀이]

# 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
    sumP = A[0]
    sumN = sum(A[1:])
    diff0 = abs(sumN - sumP)

    for i in range(2, len(A)):
        sumP += A[i-1]
        sumN -= A[i-1]

        diff_new = abs(sumP - sumN)

        if diff0 > diff_new:
            diff0 = diff_new
    return diff0