[Algorithm] 우박수열 정적분 ( Programmers - JavaScript, Python )

문제 설명

콜라츠 추측이란 로타르 콜라츠(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인 우박수열이 있다면, x = 0일때 y = k이고 다음 우박수는 x = 1에 표시합니다. 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.

 

 

 

은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. 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 = 5일경우로 예를 들어보자.

while문이 끝나면 우박수열안에는 [ [0, 5], [1, 16], [2, 8], [3, 4], [4, 2], [5, 1] ] 의 결과를 확인해 볼 수 있게 된다.

이렇게 된다면 장점은 x좌표에 대해 y좌표의 값이 명시적으로 보인다는 것이다.

[0, 5]의 경우 x = 0일경우 y = 5에 존재한다는 것이고, [1, 16]의 경우 x = 1일경우 y = 16에 존재한다. 이렇게 [5, 1]까지 확인해 볼 수 있게 된다.

 

우박수열을 구한뒤 loop를 사용함으로써 문제내에서 줬던 조건들에 부합하도록 분기처리하면 된다.

 

다만, calculator의 함수에서 계산을 진행했는데, 정적분을 해야한다. 정적분의 경우 잘 생각해보면 결국 사다리꼴 면적을 계산하는것과 동일하다.

 

 

위의 예시로 나와있던 그래프의 일부분이다. 그래프를 보면 x = 1까지 가정하고, y = 5, 16이다. 

상상력을 더해보자. x = 1, y = 16 일때 임의의 선을 한줄을 세로로 그어준다면 사다리꼴의 모양이 되는 것이 연상될 것이다.

 

(0, 5)를 상단 변, (1, 16)을 하단 변, x(0, 1)까지를 높이라고 가정한다면, 사다리꼴 계산식이 적용이 된다. 

* 사다리꼴 공식: (상단 변 + 하단 변) * 높이 / 2 

 

 

javascript

function solution(k, ranges) {
  let index = 0;
  const arr = [[index++, k]];
  while (k !== 1) {
    if (k % 2 === 0) {
      arr.push([index++, (k /= 2)]);
    } else {
      arr.push([index++, (k = k * 3 + 1)]);
    }
  }
 
  const n = arr.length - 1;
  const resultArr = [];
  for (let i = 0; i < ranges.length; ++i) {
    const [first, seconds] = ranges[i];
 
    if (first === 0 && seconds === 0) {
      resultArr.push(calculator(0, n, arr));
    } else if (first > n + seconds) {
      resultArr.push(-1);
    } else {
      resultArr.push(calculator(first, n + seconds, arr));
    }
  }
 
  function calculator(index, length, arr) {
    let result = 0;
    for (let j = index; j < length; ++j)
      result += ((arr[j][1] + arr[j + 1][1]) * (arr[j + 1][0] - arr[j][0])) / 2;
 
    return result;
  }
 
  return resultArr;
}

 

 

python

def solution(k, ranges):
    index = 0
    arr = [[index, k]]
    index += 1
 
    while k != 1:
        if k % 2 == 0:
            k = k / 2
            arr.append([index, k])
            index += 1
        else:
            k = k * 3 + 1
            arr.append([index, k])
            index += 1
 
    n = len(arr) - 1
    resultArr = []
 
    def calculator(start, end, arr):
        result = 0
        for i in range(start, end):
            result += ((arr[i][1] + arr[i + 1][1]) * (arr[i + 1][0] - arr[i][0])) / 2
        return result
 
    for i in range(len(ranges)):
        [first, seconds] = ranges[i]
 
        if first == 0 and seconds == 0:
            resultArr.append(calculator(0, n, arr))
        elif first > n + seconds:
            resultArr.append(-1)
        else:
            resultArr.append(calculator(first, n + seconds, arr))
 
    return resultArr

 

 

 

 

 

 

 

 

 

 

 

 

 

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

프로그래머스