희연's 개발 일기장

https://app.codility.com/programmers/lessons/6-sorting/triangle/

• N개의 정수로 구성된 배열 A가 주어질 때
• 만약 0 <= P < Q < R < N 이면, (P,Q,R)은 삼각형이다.
• 삼각형의 조건 = 가장 긴 변의 길이 < 다른 두 변 길이의 합
• 각 변의 다른 두 변의 합보다 작아야 한다.
• A[P] + A[Q] > A[R],
  A[Q] + A[R] > A[P],
  A[R] + A[P] > A[Q].
• 배열 A중에서, 삼각형이 존재하면 1출력, 없으면 0출력
• O(N*log(N))

def solution(A):
    A.sort()
    res = 0
    for i in range(len(A)-2):
        P,Q,R = i,i+1,i+2
        if A[P]+A[Q]>A[R] and A[P]+A[R]>A[Q] and A[Q]+A[R]>A[P]:
            res = 1
    return res

https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

• N개의 정수로 구성된 비어있지 않은 배열 A가 주어질 때
• (P, Q, R)의 곱의 결과는  A[P] * A[Q] * A[R]와 같다.
• 모든 곱의 결과 중에서 가장 큰 값을 출력하기 
• O(N * log(N))

def solution(A):
    A.sort()
    totalA = A[-1] * A[0] * A[1]
    totalB = A[-1] * A[-2] * A[-3]

    if totalA >= totalB:
        res = totalA
    else:
        res = totalB
    return res

https://app.codility.com/programmers/lessons/6-sorting/distinct/

• 배열 A가 주어질 때, 중복된 값들을 모두 제거하고 배열의 길이를 구한다.
• O(N*log(N)) or O(N)

def solution(A):
    unique = list(set(A))
    return len(unique)

https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

• 배열 A가 주어질 때, 연속되는 요소는 도로의 연속되는 자동차를 표현한 것이다.
• 배열 A에는 0(동쪽) 또는 1(서쪽)만 포함된다. 
• (P,Q) 동쪽으로 이동하는 차들이 서쪽으로 가는 자동차를 몇 번 마주치는지 구하기
• 지나가는 자동차의 쌍의 개수가 1,000,000,000개를 초과하면 -1 출력
• O(N)

def solution(A):
    cnt = 0
    total = 0
    for idx in range(len(A)):
        if idx == 1 and cnt == 0:
            continue
        if A[idx] == 0:
            cnt = cnt + 1
        else:
            total = total + cnt

    if total > 1000000000:
        return -1
    return total

https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/

• 배열 A가 주어질 때, 순열이면 1을 반환하고 아니면 0 출력하기
• O(N) or O(N * log(N))

def solution(A):
    if len(set(A)) != len(A):
        return 0

    if len(A) == max(A):
        return 1
    else:
        return 0

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

• 개구리가 강의 반대편으로 점프할 수 있는 가장 이른 시간 구하기
• 나뭇잎이 시간에 따라 떨어지는 위치 배열 A, 목표 위치 정수 X 
• 개구리는 1부터 X번까지 강 건너 모든 위치에 나뭇잎이 나타날 때만 건널 수 있다.
• ex. X = 5, 배열 A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4
  • 1에서부터 5까지 연속된 숫자로 모든 나뭇잎이 떨어져야 한다.
  • 6초일 때, 1부터 5까지 모든 나뭇잎이 깔리기 때문에 6을 출력해준다.
  • 개구리가 이동할 수 없는경우 -1 출력
• O(N)

def solution(X, A):
    arr = [0]*X
    sum = 0
    for idx, value in enumerate(A):
        if arr[value-1] == 0:
            arr[value-1] = 1
            sum = sum + 1
            if sum == X:
                return idx
    return -1

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

• N개의 정수로 이루어진 배열 A
• A[0], A[1], ..., A[P − 1]으로 합쳐진 값과 A[P], A[P + 1], ..., A[N − 1]으로 합쳐진 값들을 나눈 절대값을 구한다.
• 절대값들 중에서 가장 최소값을 출력한다.
• O(N)

def solution(A):
    res = float('inf')
    sum1 = 0
    sum2 = sum(A)
    for i in range(1,len(A)):
        sum1 += A[i-1]
        sum2 -= A[i-1]
        res = min(res, abs(sum1-sum2))
    return res

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

• N개의 서로 다른 정수로 이루어진 배열 A가 주어진다.
• A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5
• 이 배열에서 1부터 N+1까지 존재하지 않는 하나의 원소를 구한다.
• O(N) or O(N * log(N))

def solution(A):
    if len(A)==0:
        return 1
    total1 = sum(A)
    total2 = sum(range(1, len(A)+2))
    return total2-total1