희연's 개발 일기장

https://app.codility.com/programmers/lessons/12-euclidean_algorithm/chocolates_by_numbers/

• 원형으로 만들어진 초콜릿 조각 N개를 M의 간격으로 먹을 때 먹을 수 있는 초콜릿 조각의 개수
• 다음 조각의 위치는 (X+M) mod N
• N = 10, M =4 이면 0,4,8,2,6
• O(log(N + M))

def GCD(a,b):
    if(b==0):
        return a
    else:
        return GCD(b,a%b)

def solution(N, M):
    res = N // GCD(N,M)
    return res

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/min_perimeter_rectangle/

• 직사각형 면적을 나타내는 정수 N
• N = A*B
• 2*(A+B)의 값들 중에서 최소 값 찾기
• O(sqrt(N))

import math
def solution(N):
    minValue = float('inf')
    value = 0
    for D in range(1, int(math.sqrt(N))+1):
        if N % D == 0:
            if D*D == N:
                value = 2*(D+D)
                minValue = min(value, minValue)
                break
            else:
                M = N//D
                value = 2*(D+M)
                minValue = min(value, minValue)
    return minValue

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/count_factors/

• 양의 정수 N이 주어질 경우, N의 약수 개수 구하기
• O(sqrt(N))

import math
def solution(N):
    cnt = 0
    for D in range(1, int(math.sqrt(N))+1):
        if N % D == 0:
            if D*D == N:
                cnt = cnt + 1
                break
            else:
                cnt = cnt + 2
    return cnt

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

• N개의 정수로 구성된 비어 있지 않은 배열 A가 제공될 때
• (P,Q)는 A[P] + A[P+1] + ... + A[Q]
• A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0
• (3,4)의 합은 4 + 0 = 4 -> 4는 A의 slice
• A slice의 최대 값을 출력
• O(N)

def solution(A):
    res = float('-inf')
    sum = 0
    for a in A:
        sum = sum + a
        res = max(res, sum)
        sum = max(0, sum)
    return res

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

• N개의 정수로 구성된 배열 A는 주식의 일일 가격이다.
• 최대 이익 구하기
• 이익이 없는 경우 0 출력
• O(N)

def solution(A):
    min = float('inf')
    profit = 0
    maxProfit = 0

    for i in range(1, len(A)):
        if min > A[i-1]:  # min 값 구하기
            min = A[i-1]
        profit = max(0, A[i]-min) # 이익 구하기
        maxProfit = max(profit, maxProfit) # 최대 이익 구하기
    return maxProfit

https://app.codility.com/programmers/lessons/8-leader/dominator/

• N개의 정수로 구성된 배열A가 주어질 때
• 배열 A의 Dominator는 A의 요소 중 절반 이상에서 발생하는 값이다.
• A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3
• 0, 2, 4, 6, 7번째 총 5개의 인덱스에서 값으로 3을 가지고 있다.
• 8개의 정수로 구성된 배열 A에서 5는 배열의 절반 이상이기 때문에 3은 Dominator
• Dominator의 값을 출력하고, 없으면 -1 출력
• O(N*log(N)) or O(N)

def solution(A):
    if not A:
        return -1
    dict = {}

    for x in range(len(A)):
        dict[A[x]] = dict.get(A[x], 0) + 1
        if dict[A[x]] > len(A)//2:
            return x
    return -1

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

• N개의 문자로 구성된 문자열 S는 다음과 같이 properly nested
  • S는 비어있다.
  • S는 "(U)" 형식을 갖고 있다. U는 properly nested
  • S는 V와 W가 적절하게 중첩된 문자열인 "VW" 형식을 갖는다.
• 문자열 S가 적절하게 properly nested 되면 1 출력 아니면 0 출력
• O(N)

def solution(S):
    stack = []
    for i in range(len(S)):
        input = S[i]
        if input == ')':
            if len(stack)==0:
                return 0
            if stack[-1]=='(':
                stack.pop()
        else:
            stack.append(input)
    if len(stack)==0:
        return 1
    else:
        return 0

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