Lesson 3: Time Complexity

[Lesson 3: Time Complexity]

Tasks 1. TapeEquilibrium

Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

사이트 : https://codility.com/programmers/task/tape_equilibrium/

난이도 : PAINLESS

추가 자료 : Open reading material (PDF)

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| In other words, it is the absolute difference between the sum of the first part and the sum of the second part. For example, consider array A such that:   A[0] = 3   A[1] = 1   A[2] = 2   A[3] = 4   A[4] = 3 We can split this tape in four places: P = 1, difference = |3 − 10| = 7  P = 2, difference = |4 − 9| = 5  P = 3, difference = |6 − 7| = 1  P = 4, difference = |10 − 3| = 7  Write a function: def solution(A) that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved. For example, given:   A[0] = 3   A[1] = 1   A[2] = 2   A[3] = 4   A[4] = 3 the function should return 1, as explained above. Assume that: N is an integer within the range [2..100,000]; each element of array A is an integer within the range [−1,000..1,000]. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

def solution(A):
    # P = 1
    prevSum = A[0]
    postSum = 0
    for index in range(1, len(A)):
        postSum += A[index]
    min = abs(prevSum - postSum)
 
    # 1<P<=len(A)
    for index in range(1, len(A)-1):
        prevSum += A[index]
        postSum -= A[index]
        diff = abs(prevSum - postSum)
        if min > diff:    min = diff
    return min

먼저, P가 1일 경우를 계산하여 기준을 잡아준다.

그 뒤부터 값을 하나씩 prevSum에 더해주고 postSum에 빼주는 방식으로 진행한다.

SCORE: 100%

Tasks 2. FrogJmp

Count minimal number of jumps from position X to Y.

사이트 : https://codility.com/programmers/task/frog_jmp/

난이도 : PAINLESS

추가 자료 : Open reading material (PDF)

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target. Write a function: def solution(X, Y, D) that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y. For example, given:   X = 10   Y = 85   D = 30 the function should return 3, because the frog will be positioned as follows: after the first jump, at position 10 + 30 = 40 after the second jump, at position 10 + 30 + 30 = 70 after the third jump, at position 10 + 30 + 30 + 30 = 100 Assume that: X, Y and D are integers within the range [1..1,000,000,000]; X ≤ Y. Complexity: expected worst-case time complexity is O(1); expected worst-case space complexity is O(1).

#1

def solution(X, Y, D):
    cnt = 0
    while X < Y:
        X += D
        cnt += 1
    return cnt

현재 개구리의 위치 X를 원하는 거리 Y에 도달할 때까지 D를 더하는 것을 반복시켜 준다.

이때 반복한 횟수만큼 cnt를 증가시켜 준다.

SCORE: 55%

- 시간 초과

#2

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

차이를 계산해 준 뒤 나누어 떨어진다면 몫을 그대로, 나누어 떨어지지 않는다면 몫에 1을 더해 리턴한다.

SCORE: 100%

Tasks 3. PermMissingElem

Find the missing element in a given permutation.

사이트 : https://codility.com/programmers/task/perm_missing_elem/

난이도 : PAINLESS

추가 자료 : Open reading material (PDF)

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing. Your goal is to find that missing element. Write a function: def solution(A, N) that, given a zero-indexed array A, returns the value of the missing element. For example, given array A such that:   A[0] = 2   A[1] = 3   A[2] = 1   A[3] = 5 the function should return 4, as it is the missing element. Assume that: N is an integer within the range [0..100,000]; the elements of A are all distinct; each element of array A is an integer within the range [1..(N + 1)]. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

#1

def solution(A):
    result = []
    for index in range(1, len(A)+2):
        result.append(index)
    for num in A:
        result.remove(num)
    return result.pop()

범위 내의 값을 모두 가지고 있는 배열 result를 만들어 준다.

그리고 A에 해당하는 값을 하나씩 지워나간 뒤 마지막에 남은 값을 리턴시켜준다.

SCORE: 60% - The following issues have been detected: timeout errors.

#2

def solution(A):
    A.sort()
    for index in range(len(A)):
        if A[index] != index+1:
            return index+1
    return len(A)+1

정렬해 준 뒤, 작은 수부터 차례로 비어있는 값을 검색한다.

SCORE: 100%