우박수열 정적분

업데이트 사항

수정 : 2024-07-04 [시간 복잡도 추가]

 

 

코딩테스트 연습 - 우박수열 정적분 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 코드

# 2024-07-04
def collatz(number):
    answer=[number]
    while True:
        if number%2==0:
            number//=2
        else:
            number=(number*3)+1
        answer.append(number)
        if number==1:
            break
    print(answer)
    return answer

def solution(k, ranges):
    answer=[]
    collatz_list = collatz(k)
    size = [(collatz_list[i]+collatz_list[i+1])/2 for i in range(len(collatz_list)-1)]
    
    n = len(size)
    for rg in ranges:
        start, end = rg
        end=n+end
        if start>end:
            answer.append(-1)
        elif start==end:
            answer.append(0)
        else:
            answer.append(sum(size[start:end]))

    return answer

 

시간 복잡도

1. collatz_list : 콜라츠 리스트 생성 >> k 가 1이 될떄까지 반복 (선형시간)

2. size : 넓이 리스트 생성 >> 역시 모든 콜라츠 리스트를 탐색하므로 (선형시간)

3. for rg in ranges : ranges 리스트를 순회하며 최종 넓이를 계산 >> 모든 ranges 리스트를 순회하며 size배열을 해당범위를 순회하며 합을 계산하므로 (이차형 시간)

 

즉, 최종 시간 복잡도는 이차형시간 복잡도 입니다. ( O(n2) )