프로그래머스 우박수열 정적분

문제 설명

콜라츠 추측이란 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로 모든 자연수 n에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측입니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.

예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.

수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다. 현재 이 추측이 참인지 거짓인지 증명되지 않았지만 약 1해까지의 수에서 반례가 없음이 밝혀져 있습니다.

은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다. 초항이 K인 우박수열이 있다면, x = 0일때 y = K이고 다음 우박수는 x = 1에 표시합니다. 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.

은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. x에 대한 어떤 범위 [a, b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적과 같습니다. 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에 대해서 우박수열 정적분을 해보려고 합니다.

단, 우박수열 그래프의 가로축 길이를 미리 알 수 없기 때문에 구간의 시작은 음이 아닌 정수, 구간의 끝은 양이 아닌 정수로 표현합니다. 이는 각각 꺾은선 그래프가 시작하는 점과 끝나는 점의 x좌표에 대한 상대적인 오프셋을 의미합니다.

예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

제한 사항

• 2 ≤ k ≤ 10,000
• 1 ≤ ranges의 길이 ≤ 10,000
  • ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
• 주어진 모든 입력에 대해 정적분의 결과는 227 을 넘지 않습니다.
• 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.

입출력 예

k	ranges	result
5	[[0,0],[0,-1],[2,-3],[3,-3]]	[33.0,31.5,0.0,-1.0]

입출력 예 설명

입출력 예 #1

5로 시작하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 그래프에서 꺾이는 지점을 경계로 5개의 구역으로 나눠보면 각각의 구간 넓이는 10.5, 12, 6, 3, 1.5 입니다.

무지성 풀이

• 어라? 한번에 통과된 건 처음인데?

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

    k_range = len(k_list)
    
    def hailstorm_memoization(n,memo={}):
        if n in memo:
            return memo[n]
        else:
            memo[n] = min(k_list[n],k_list[n+1]) + abs(k_list[n] - k_list[n+1])/2
        return memo[n]
        
    for i in range(len(ranges)):
        a = ranges[i][0]
        b = ranges[i][1] + k_range - 1
        _tmp = 0
        if a < b:
            for i in range(a, b):
                _tmp += hailstorm_memoization(i)
        elif a > b:
            _tmp = -1
        answer.append(_tmp)
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (1.29ms, 10.3MB)
테스트 3 〉	통과 (38.30ms, 12.3MB)
테스트 4 〉	통과 (2.50ms, 10.6MB)
테스트 5 〉	통과 (0.98ms, 10.3MB)
테스트 6 〉	통과 (7.37ms, 10.8MB)
테스트 7 〉	통과 (40.97ms, 12.2MB)
테스트 8 〉	통과 (45.02ms, 12.4MB)
테스트 9 〉	통과 (0.28ms, 10.2MB)
테스트 10 〉	통과 (11.47ms, 10.8MB)

• 근데 다른 고수들의 풀이를 보니...
• 헐? 메모 안해도 되나봐?
• 아... 그 앞에까지 합을 다 더해놓고, 빼는구나? 대박!

from itertools import accumulate

def collas(k):
    coord = []
    while k != 1:
        coord.append(k)
        if k % 2:
            k = k * 3 + 1
        else:
            k //= 2
    coord.append(k)
    return coord

def solution(k, ranges):
    coord = collas(k)
    area = []
    for i in range(len(coord) - 1):
        area.append((coord[i] + coord[i+1])/2)
    area = [0] + list(accumulate(area))
    n = len(area) - 1
    result = []
    for i, j in ranges:
        k = n + j
        if i > k:
            result.append(-1)
        elif i == k:
            result.append(0)
        else:
            result.append(area[k] - area[i])
    return result
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.4MB)
테스트 2 〉	통과 (0.09ms, 10.3MB)
테스트 3 〉	통과 (1.43ms, 12.4MB)
테스트 4 〉	통과 (0.24ms, 10.3MB)
테스트 5 〉	통과 (0.12ms, 10.4MB)
테스트 6 〉	통과 (0.45ms, 10.6MB)
테스트 7 〉	통과 (1.49ms, 12MB)
테스트 8 〉	통과 (2.64ms, 12.5MB)
테스트 9 〉	통과 (0.09ms, 10.4MB)
테스트 10 〉	통과 (0.97ms, 11MB)

def solution(k, ranges):
    answer = []
    arr = [k]
    while k > 1:
        if not k % 2: k //= 2
        else: k = k*3+1
        arr.append(k)
    area = [0]
    for i in range(len(arr)-1):
        area.append(area[-1]+(arr[i]+arr[i+1])/2)
    for a, b in ranges:
        if a >= len(area) or b-1 < -len(area): answer.append(-1)
        elif area[b-1]-area[a] < 0: answer.append(-1)
        else: answer.append(area[b-1]-area[a])
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.20ms, 10.4MB)
테스트 3 〉	통과 (3.45ms, 12.3MB)
테스트 4 〉	통과 (0.73ms, 10.5MB)
테스트 5 〉	통과 (0.27ms, 10MB)
테스트 6 〉	통과 (1.05ms, 10.8MB)
테스트 7 〉	통과 (5.39ms, 11.9MB)
테스트 8 〉	통과 (5.75ms, 12.3MB)
테스트 9 〉	통과 (0.09ms, 10.1MB)
테스트 10 〉	통과 (1.22ms, 10.9MB)

• 내 코드에서 메모이제이션만 빼면?
• for문이 하나 있어서 안 빨라짐.

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

    for n in range(len(k_list)-1):
        k_list[n] = (k_list[n] + k_list[n+1])/2 # 이걸 왜 어렵게 생각했을까...
    
    lk = len(k_list) - 1
    for a, b in ranges:
        b += lk
        if a < b:
            _tmp = 0
            for i in range(a, b): # 이 부분 때문에 느려짐.
                _tmp += k_list[i]
            answer.append(_tmp)
        elif a > b:
            answer.append(-1)
        if a == b:
            answer.append(0)
    return answer

• 그래도 아까 것 보다 빠르긴 하다.
• 효율성 테스트가 없으면 그냥 for문 적게 돌리는 방식으로 짜는게 제일 좋은 것 같다.

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.40ms, 10.3MB)
테스트 3 〉	통과 (15.82ms, 12.1MB)
테스트 4 〉	통과 (1.16ms, 10.4MB)
테스트 5 〉	통과 (0.67ms, 10.2MB)
테스트 6 〉	통과 (3.17ms, 10.6MB)
테스트 7 〉	통과 (18.05ms, 12MB)
테스트 8 〉	통과 (18.10ms, 12.2MB)
테스트 9 〉	통과 (0.14ms, 10.1MB)
테스트 10 〉	통과 (4.23ms, 10.8MB)

 수포자의 정적분 ㅠ.ㅠ