우박수열 정적분(프로그래머스) 문제풀이

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/134239

프로그래머스

 

 

 

문제 접근 방식

특정 수 k에 대한 우박 수열을 구하고, 해당 수열에 대한 그래프에 대해 특정 구간 [a,b] 에서의 정적분을 구하는 문제이다. 요약하면 우박 수열 그래프의 특정 구간에서의 면적을 구하는 문제이다. 

 

문제에서 우박수열을 어떻게 구하는지에 대한 설명을 아래와 같이 제공줬으며 이를 코드로 구현하면 된다.

 

최종적으로 특정 구간에서의 면적을 구하기 위해서는 각 [i,i+1] (x는 0이상) 에 대한 면적을 미리 구할 필요가 있다. 이를 위해서 우박수열을 구할 때  이전항 (x=i-1)과 현재항(x= i) 를 통해 [i,i+1]의 면적을 구해놓은 후, [a,b]가 주어졌을 때 해당 구간의 면적들을 모두 더해주면 [a,b]구간의 정적분을 구할 수 있다. 

 

이때 조심해야할 부분은 정적분 구간 [a,b] 에서 b가 a보다 작은 경우이다. 해당 경우는 문제에서 -1을 반환하라고 하였다.

 

 

시간 복잡도

우박수열의 끝 항 n의 최댓값을 예상할 수가 없어서 시간 복잡도를 따로 생각하지는 않았다. 만약 시간초과가 났을 경우 각 구간의 합을 세그먼트 트리 자료구조로 만들어서 구간 합을 구하는 시간을 단축시킬 예정이었으나, 기본 sum을 사용해서도 통과를 했기 때문에 따로 처리해주지는 않았다.

 

 

코드

# 우박 수열을 구하면서, 해당 그래프의 [i,i+1]의 면적을 areas에 저장 후, 끝 항 n을 반환한다.
def collatz(k ,areas):
    count =0
    while True:
        if k== 1:
            break

        previous = k
        if k % 2 == 0:
            k //= 2
        else:
            k = k * 3 + 1
        areas.append((previous + k) / 2)
        count += 1

    return count


def solution(k, ranges):
    areas = []
    n = collatz(k, areas)

    answer = []

    for a, b in ranges:
        start, end = a, n + b
        if start <= end:
            answer.append(sum(areas[start:end]))
        else:
            answer.append(-1)

    return answer