알고리즘 코드카타 129 - 우박수열 정적분

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

프로그래머스

 

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

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.
예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.

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

k = 5인 경우의 우박수열 그래프

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

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

예를 들어, 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이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.

 

 

def hail(num, n):
    for _ in range(n):
        if num % 2 == 0:
            num = num / 2
        else:
            num = num * 3 + 1    
    return num

 

먼저 우박수열을 구현하는 함수를 만들어준다. 간단하게 짝수라면 반으로 나누어주고 홀수라면 3을 곱하고 1을 더하는 함수이다.

 

def find_n(num):
    n = 0
    while True:
        n += 1
        if hail(num,n) == 1:
            return n

 

다음으로 주어진 수k가 우박수열을 통해서 1이 되는 값 n을 구하기 위한 함수를 작성한다. n을 1씩 증가시켜서 값이 1이 될때의 n값을 반환하도록한다. (문제의 조건을 고려해보았을 때, 주어지는 모든 정수는 콜라스추측을 만족하기 때문에 예외처리는 하지 않았다.)

 

def solution(k, ranges):
    answer = []
    n = find_n(k)

 

위에서 작성한 find_n함수를 이용해서 n값을 구할 수 있다.

 

# def solution(k, ranges):
#     answer = []
#     n = find_n(k)
    for r in ranges:
        a, b = r
        integral = 0
        for i in range(a, n+b):
            y_1 = max(hail(k, i), hail(k, i+1))
            y_2 = min(hail(k, i), hail(k, i+1))
            integral += y_2+(y_1-y_2)/2
        answer.append(integral)
    
    return answer

 

range의 주어진 범위에 대해서 정적분을 수행한다. 하지만 정적분은 결국 특정 구간의 넓이를 구하는 것이기때문에 실제로 정적분을 코드로 구현할 필요는 없다. 주어진 구간은 모두 직선으로 둘러쌓여있기 때문에 간단하게 넓이를 구할 수 있기 때문이다.

우박수열의 각 구간은 모두 직사각형과 삼각형의 조합으로 이루어져 있다. 하나의 구간의 가로길이는 항상 1이므로 직사각형의 넓이는 1*(두 y값중 작은 값)이 된다. 삼각형의 넓이역시 마찬가지로 가로길이가 항상 1이기 때문에 1*(두 y값중 큰 값 - 두 y값중 작은 값)/2가 된다.

위의 코드는 앞에서 설명한 넓이구하는 방식을 그대로 구현한 것이다. 따라서 해당 구간들을 각각 반복해서 더한 후 answer에 더해준다면 해당 구간의 넓이를 구할 수 있다.

 

# def solution(k, ranges):
#     answer = []
#     n = find_n(k)
    # for r in ranges:
    #     a, b = r
        if a <= n+b:
            # integral = 0
            # for i in range(a, n+b):
            #     y_1 = max(hail(k, i), hail(k, i+1))
            #     y_2 = min(hail(k, i), hail(k, i+1))
            #     integral += y_2+(y_1-y_2)/2
        else:
            integral = -1
        # answer.append(integral)
    
    # return answer

 

마지막으로 예외처리를 해준다. 일반적인 정적분의 경우 시작점이 도착점보다 앞서있을 경우 음의 넓이를 반환하지만 문제에서는 위의 경우에는 -1을 반환하도록 지시하고 있으므로 -1을 입력하고 answer에 추가해준다.

 

크아아악

 

아쉽게도 해당 방법은 시간초과가 나오고 말았다. 아마도 각 구간의 넓이를 구하면서 정적분을 반복하는데, 이미 계산이 끝난 범위도 반복해서 계산하고 있기 때문이다.

 

# def solution(k, ranges):
#     answer = []
#     n = find_n(k)
    integrate_function = []
    for i in range(n):
        y_1 = max(hail(k, i), hail(k, i+1))
        y_2 = min(hail(k, i), hail(k, i+1))
        integrate_function.append(y_2+(y_1-y_2)/2)
    
    # return answer

 

그래서 각 구간의 넓이를 필요할때마다 다시 계산하지 않고 모든 구간의 넓이를 한번에 구하기로 했다. 모든 구간의 넓이를 저장하고 있는 리스트를 작성하고 필요할 때마다 해당 리스트에서 미리 계산되어 있는 값을 호출하면 계산량을 줄일 수 있을 것이다.

 

# def solution(k, ranges):
#     answer = []
#     n = find_n(k)
    # integrate_function = []
    # for i in range(n):
    #     y_1 = max(hail(k, i), hail(k, i+1))
    #     y_2 = min(hail(k, i), hail(k, i+1))
    #     integrate_function.append(y_2+(y_1-y_2)/2)
    
    # for r in ranges:
    #     a, b = r
    #     if a <= n+b:
            integral = sum(integrate_function[a:n+b])
        # else:
        #     integral = -1               
        # answer.append(integral)
    
    # return answer

 

이제 올바른 구간이 주어진 경우 새로값을 계산하지 않고 이미 계산되어있는 값들을 더해서 값을 반환할 수 있다.

완료!

 

 

문제풀이보다 문제의 설명을 이해하는 것이 더 오래 걸렸던 문제였다. 그리고 오랜만에 적분을 이용해볼 수 있었던 문제였다. 적분이라기 보다는 그냥 넓이구하기정도였지만...