[파이썬] 프로그래머스 : 우박수열 정적분 (Lv.2)

[파이썬] 프로그래머스 : 우박수열 정적분 (Lv.2)

 

프로그래머스

 

---

풀이

0. 방향성 생각

누적합을 활용해서 구간합을 구한다.

 

1. 주어진 수열 완성, 누적합 구하기

def solution(k,ranges):
    
    arr,cum,answer = [k],[],[]
    while arr[-1] > 1 :
        if arr[-1]%2==0 :
            arr.append(arr[-1]//2)
        else :
            arr.append(arr[-1]*3+1)

    for i in range(len(arr)-1):
        if i==0 : cum.append((arr[0]+arr[1])/2)
        else : cum.append(cum[-1]+(arr[i+1]+arr[i])/2)

 

2. 방향성 생각

    d = len(cum)
    cum = [0] + cum
    for start,temp in ranges:
        end = d+temp
        if end == start :
            answer.append(0)
        elif end < start :
            answer.append(-1)
        else:
            answer.append(cum[end]-cum[start])
    return answer

주어진 수열의 길이를 d라고 먼저 정의한다.

구간합에서 첫 값이 0이 이어야한다. 이를 처리해준다.

ranges의 뒤의 값 temp는 0또는 음수이므로 인덱싱 할 때 처럼 start부터 temp+d까지이다.
오류 안나게 케이스만 잘 조절해주면 된다.

---

전체코드

def solution(k,ranges):
    
    arr,cum,answer = [k],[],[]
    while arr[-1] > 1 :
        if arr[-1]%2==0 :
            arr.append(arr[-1]//2)
        else :
            arr.append(arr[-1]*3+1)

    for i in range(len(arr)-1):
        if i==0 : cum.append((arr[0]+arr[1])/2)
        else : cum.append(cum[-1]+(arr[i+1]+arr[i])/2)

    d = len(cum)
    cum = [0] + cum
    for start,temp in ranges:
        end = d+temp
        if end == start :
            answer.append(0)
        elif end < start :
            answer.append(-1)
        else:
            answer.append(cum[end]-cum[start])
    return answer

코멘트