희연's 개발 일기장

https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

• N개의 문자로 구성된 문자열 S가 주어질 때
• 아래의 조건 중에서 하나의 조건이라도 만족하면 properly nested
  • S는 비어있다.
  • S는 "(U)" or "[U]" or "{U}" 형식을 가지면 U는 properly nested.
  • S는 V와 W가 적절하게 중첩된 문자열인 "VM" 형식을 가지면 V와 W는 properly nested 
• properly nested인 경우 1출력, 아닌 경우 0출력
• O(N)

def solution(S):
    stack = []
    for i in range(0, len(S)):
        input = S[i]
        if input=='(' or input=='[' or input=='{':
            stack.append(input)
        if len(stack) == 0:
            return 0

        if input==')':
            if stack.pop()!='(':
                return 0
        elif input==']':
            if stack.pop() !='[':
                return 0
        elif input=='}':
            if stack.pop() !='{':
                return 0
    if len(stack)==0:
        return 1
    else:
        return 0

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