동전줍기 & 채점하기

2019-01-25

Algorithm

동전 줍기

길에 떨어져 있는 많은 동전들의 위치와 갯수를 의미하는 리스트 A가 있습니다.

당신은 길위에 동전을 수집하려고 합니다.

출발하는 위치 k와 이동가능한 거리를 m이 주어질때,
가장 많은 동전을 획득하려고하면 몇개를 획득할 수 있는지 알려주는 함수를 만드세요.

예를 들어 리스트 A와 k, m이 아래와 같을때

1
2
3

A = [2, 3, 7, 5, 1, 3, 9]
k=4
m=6

가장 많은 동전을 주울수있는 방법은 아래와 같고

4번째에서 출발 - 1개 획득 
왼쪽으로 이동  - 5개 획득 (1번이동)
왼쪽으로 이동  - 7개 획득 (2번이동)
오른쪽으로 이동 - 0개 획득 (3번이동)
오른쪽으로 이동 - 0개 획득 (4번이동)
오른쪽으로 이동 - 3개 획득 (5번이동)
오른쪽으로 이동 - 9개 획득 (6번이동)

총
1, 5, 7, 3, 9 = 25개의 버섯을 주울 수 있다.

25를 리턴하는 함수 solution을 생성하세요.

조건

def solution(A, k, m):

1 <= len(A) <= 10**5

0 <= k, m <= 10**5

나의 풀이

def solution(A, k, m):
    acc_ls = []
    sum = A[k]
    for i in range(k-1,-1,-1):
        sum += A[i]
        acc_ls.append(sum)
    acc_ls = sorted(acc_ls, reverse=True)
    acc_ls.append(A[k])

    sum = 0
    for j in range(k+1,len(A)):
        sum += A[j]
        acc_ls.append(sum)
    
    result = 0
    min = k - m
    if min < 0:
        min = 0
    max = k + m
    if max > len(A)-1:
        max = len(A)-1
    result = A[min]
    if result < A[max]:
        result = A[max]
    
    for i in range(1, round(m/2)):
        up = i
        down = m - 2*i
        if up + down > m:
            continue
        try:
            if acc_ls[k+up] + acc_ls[k-down] > result:
                result = acc_ls[k+up] + acc_ls[k-down]
            if acc_ls[k-up] + acc_ls[k+down] > result:
                result = acc_ls[k-up] + acc_ls[k+down]
        except:
            continue
    
    return result

강사님 풀이

from math import ceil

def accumulate(A):
    result = [0]
    for a in A:
        result.append(result[-1]+a)
    return result

def range_sum(A, x, y):
    return A[y+1] - A[x]

def solution(A, k, m):
    acc_A = accumulate(A)
    
    result = A[k]
    
    # 왼쪽으로 출발 후에 오른쪽으로 방향 이동
    for left in range(0, ceil(m/2)): # 왼쪽으로 0번 이동한 것 포함, 즉 오른쪽으로만 이동한 경우 포함
        right = m - (left*2)
        
        left_idx = max(k-left, 0) # IndexError 방지
        right_idx = min(len(A)-1, k+right) # IndexError 방지
        
        result = max(result, range_sum(acc_A, left_idx, right_idx))
    
    # 오른쪽으로 출발 후에 왼쪽으로 방향 이동
    # 동일하게 작성
    return result

채점하기

매주 금요일 알고리즘 테스트 결과를 채점하기 귀찮아졌습니다.

그래서 직접하지 않고, 수강생분들에게 공부가 된다는 사탕발림으로 서로의 시험결과를 채점하게 하려고합니다.

단, 양심적으로 진행하기 위해서 그 누구도 자신의 시험을 채점하지 않는다고 할때.

채점할 수 있는 경우의 수를 구하는 함수를 구하세요.

는

n=1일때 0개
n=2일때 1개
그리고 n>=3일때

(n-1) * ( (n-1)명이서 서로 채점하는 경우의 수 + (n-2)명이서 서로 채점하는 경우의 수)) 라는 특징을 따른다고 합니다.

def solution(n):함수를 생성하세요.

조건

1 <= n <= 1000

def solution(n):
    if n <= 2:
        return n-1
    return (n-1) * (solution(n-1) + solution(n-2))

memorization function 중요

def deco(func):
    m = {}
    def inner(n):
        if not m.get(n):
            result = func(n)
            m[n] = result
        return m[n]
    return inner

@deco
def solution(n):
    if n <= 2:
        return n-1
    return (n-1) * (solution(n-1) + solution(n-2))

코드 실행시간 정확히 측정하는법

import time

start = time.perf_counter()

end = time.perf_counter()

end - start