링크
https://school.programmers.co.kr/learn/courses/30/lessons/134239
문제
콜라츠 추측이란 로타르 콜라츠(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로 정의한다.
문제 풀이
문제를 해결하기 위해서 우선 콜라츠 추측에 따라서 우박수열들을 구한다. 구한 값들을 집합에 저장하여 값들을 저장해놓는다. 주어진 숫자가 1이 될때까지 위의 방법으로 값을 계산한 뒤에 과정을 거치며 나온 숫자들을 저장해놓도록 한다.
우박수열을 구하면 각 구간별로 정적분을 진행한다.
전체 면적을 한번에 구할 수 없기 때문에 각 구간별로 사다리꼴 모양으로 나누어서 면적을 구한다.
사다리꼴 면적 = (윗변 x 아랫변) x 높이 % 2
각각의 면적을 구하면 왼쪽부터 차례로 [ 10.5, 12, 6, 3, 1.5 ] 이다.
이제 주어진 범위에 대해서 면적을 구한다.
범위는 [i, j]로 주어진다.
주어진 값에 대해서 실제 범위를 구하면 [i, 나누어진 구간 수 - j] 가 된다.
범위에 포함되는 사다리꼴 면적을 모두 더해서 원하는 범위의 면적을 구한다.
주의할 점은 새로 계산된 범위가 왼쪽이 오른쪽 보다 작다면 -1.0을 나타내고, 두 값이 같다면 0.0을 나타내도록 한다.
코드
function solution(k, ranges) {
let result = []
let collatz = [k]
let integral = []
let count = 0
// 우박수열 구하기
while(k !== 1) {
if(k % 2 === 0) {
k = k / 2
} else {
k = k * 3 + 1
}
collatz.push(k)
count++
}
// 구간 별 면적 구하기
for(let i = 0; i < collatz.length - 1; i++) {
integral.push( (collatz[i] + collatz[i + 1]) / 2 )
}
// ranges로 주어진 구간 별 면적 구하기
ranges.map(el => {
const left = el[0]
const right = integral.length + el[1]
if(left === right) {
result.push(0.0)
}
else if(left > right) {
result.push(-1.0)
}
else {
let sum = 0.0
for(let i = left; i < right; i++)
sum += integral[i]
result.push(sum)
}
})
return result
}