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

Programmers | Level 2 | 우박수열 정적분
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Math
Description
콜라츠 추측이란 로타르 콜라츠(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로 정의합니다.
Constraints
- 2 ≤
k
≤ 10,000 - 1 ≤
ranges
의 길이 ≤ 10,000ranges
의 원소는[a, b]
형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
- 주어진 모든 입력에 대해 정적분의 결과는 2^27 을 넘지 않습니다.
- 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분
.0
이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.
Examples
k | ranges | result |
---|---|---|
5 | [[0, 0], [0, -1], [2, -3], [3, -3]] | [33.0, 31.5, 0.0, -1.0] |
3 | [[0, 0], [1, -2], [3, -3]] | [47.0, 36.0, 12.0] |
Solutions
Code
import java.util.*;
class Solution {
public double[] solution(int k, int[][] ranges) {
List<Double> areas = collatzAreas(k); // 우박수열의 각 구간 면적을 계산
int n = areas.size(); // 전체 면적 리스트의 크기
double[] result = new double[ranges.length]; // 구간 별 면적 저장 배열
// 각 구간의 면적을 계산하여 결과 배열에 저장
for (int i = 0; i < ranges.length; i++) {
int start = ranges[i][0];
int end = n + ranges[i][1];
result[i] = sumAreas(start, end, areas);
}
return result;
}
// 주어진 시작점과 끝점 사이의 면적 합을 계산하는 함수
private double sumAreas(int start, int end, List<Double> areas) {
if (start > end) return -1; // 구간이 유효하지 않을 경우 -1 반환
double totalArea = 0;
for (int j = start; j < end; j++) {
totalArea += areas.get(j); // 각 구간의 면적을 더함
}
return totalArea;
}
// 주어진 k에 대해 우박수열을 생성하고, 각 구간의 면적을 계산하여 리스트로 반환
private List<Double> collatzAreas(int k) {
List<Double> areas = new ArrayList<>(); // 각 구간의 면적을 저장할 리스트
int prev = k; // 이전 y값 (초기값은 k)
// 우박수열을 계산하며 각 구간의 면적을 구함
while (k > 1) {
if (k % 2 == 0) {
k /= 2; // 짝수일 경우 2로 나눔
} else {
k = k * 3 + 1; // 홀수일 경우 3을 곱하고 1을 더함
}
// 이전 값과 현재 값을 이용하여 면적 계산
double area = (prev + k) / 2.0; // 두 y값을 이용해 구간 면적 계산
areas.add(area); // 면적 리스트에 추가
prev = k; // 현재 값을 이전 값으로 업데이트
}
return areas; // 모든 구간의 면적 리스트 반환
}
}
Approaches
이 문제는 수열 생성과 정적분 계산을 결합한 수학적 문제입니다.
1. 문제 분석
우박수열 문제는 콜라츠 추측을 기반으로 주어진 수 k를 이용하여 수열을 생성하고, 그 수열을 꺾은선 그래프로 표현한 후, 특정 구간에 대한 정적분을 구하는 문제입니다. 콜라츠 추측은 임의의 자연수 k
에 대해 특정 규칙에 따라 숫자를 변화시키면서 최종적으로 항상 1
에 도달한다고 추정되는 수열입니다. 이 수열의 변화 과정을 좌표 평면 위에 꺾은선 그래프로 표현하고, 주어진 구간에 대해 해당 꺾은선 그래프의 면적을 계산하는 것이 문제의 목표입니다.
우박수열의 각 값들은 (x, y)
좌표로 표현됩니다. x
는 시간의 흐름을, y
는 수열의 값을 나타냅니다. 즉, x
가 증가할수록 수열의 다음 값이 y
좌표에 찍히게 됩니다. 예를 들어, k = 5
인 경우 우박수열은 [5, 16, 8, 4, 2, 1]
로 나타나며, 이 값들을 그래프로 그리면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1)과 같이 각 x 좌표와 y 값으로 표현됩니다.
문제의 핵심은, 이 꺾은선 그래프를 기반으로 각 구간의 면적을 구하는 것입니다. 꺾은선 그래프의 각 구간은 인접한 두 점 (x1, y1)
과 (x2, y2)
를 잇는 직선으로 연결됩니다. 이 구간의 면적은 직선 아래쪽 영역의 넓이로 정의되며, 이는 사다리꼴의 면적으로 계산할 수 있습니다. 두 점 (x1, y1)
, (x2, y2)
를 잇는 직선 구간의 면적은 다음과 같이 구할 수 있습니다:
면적 = (y1 + y2) / 2 * (x2 - x1)
따라서, 각 구간에 대한 면적을 누적하여 주어진 범위 [a, b]
에 대한 정적분을 계산하면 됩니다. 만약 구간의 시작점이 끝점보다 크거나, 범위가 유효하지 않은 경우 해당 구간의 정적분 값은 -1
로 정의합니다.
또한, 주어진 구간의 표현 방식은 [a, b]
형태로, a
는 정적분을 시작하는 x 좌표, b
는 끝점에서의 역방향 오프셋을 나타냅니다. 예를 들어, b = -1
일 경우는 끝점에서 1칸 이전의 위치를 의미합니다. 이를 고려하여 정확한 구간의 범위를 설정하고, 각 범위에 대한 면적을 계산해야 합니다.
정리하자면, 이 문제는 주어진 k
를 기반으로 우박수열을 생성하고, 각 구간에 대해 꺾은선 그래프의 면적을 계산한 후, 주어진 구간별로 정적분 결과를 반환하는 것이 목표입니다. 면적을 계산할 때는 사다리꼴 공식과 구간의 유효성을 확인하는 것이 중요하며, 유효하지 않은 구간일 때는 결과를 -1
로 처리해야 합니다.
2. 접근 방식
우박수열을 생성하고 그에 따른 면적을 계산한 후, 주어진 구간별 면적을 구하는 방식으로 접근합니다. 각 단계는 다음과 같습니다:
- 우박수열 생성: 주어진
k
로 콜라츠 추측에 따라 우박수열을 생성하고, 수열의 각 변화에 따른 구간의 면적을 계산하여 리스트에 저장합니다. - 면적 리스트 생성: 각 구간의 시작점과 끝점을 기준으로 두 y값의 평균을 구하여 사다리꼴의 면적을 계산하고, 이를 리스트에 저장합니다.
- 구간별 면적 계산: 주어진
ranges
에 대해 시작점과 끝점을 기준으로 구간 내의 면적을 계산합니다. 만약 시작점이 끝점보다 크면, 이는 유효하지 않은 구간으로 판단하고 결과값을-1
로 정의합니다. - 최종 결과 반환: 모든 구간에 대한 면적 합을 계산한 후, 결과를 배열 형태로 반환합니다.
3. 우박수열 생성 및 면적 계산
주어진 k
값으로 시작하여, 콜라츠 추측의 규칙을 따라 우박수열을 생성하고, 각 구간의 면적을 계산합니다. 수열을 확장하며 두 인접한 y값의 평균을 구해 구간의 면적으로 기록합니다. 이 과정을 통해 각 구간의 면적을 리스트로 저장할 수 있습니다.
private List<Double> collatzAreas(int k) {
List<Double> areas = new ArrayList<>(); // 각 구간의 면적을 저장할 리스트
int prev = k; // 초기 y값 (k값)
// 우박수열 계산 및 각 구간의 면적 계산
while (k > 1) {
if (k % 2 == 0) {
k /= 2; // 짝수일 경우 2로 나눔
} else {
k = k * 3 + 1; // 홀수일 경우 3을 곱하고 1을 더함
}
double area = (prev + k) / 2.0; // 두 y값을 이용해 면적 계산
areas.add(area); // 리스트에 면적 추가
prev = k; // 이전 값을 현재 값으로 갱신
}
return areas; // 모든 구간의 면적 리스트 반환
}
4. 정적분 구간에 대한 면적 합 계산
ranges
에 주어진 각 구간에 대해 정적분을 구하는 과정입니다. 각 구간의 시작점과 끝점을 기준으로 구간 내의 면적을 더하고, 유효하지 않은 구간일 경우 -1
을 반환하도록 합니다.
private double sumAreas(int start, int end, List<Double> areas) {
if (start > end) return -1; // 시작점이 끝점보다 크면 유효하지 않은 구간
double totalArea = 0;
for (int j = start; j < end; j++) {
totalArea += areas.get(j); // 구간 내의 면적을 모두 합산
}
return totalArea;
}
5. 최종 결과 도출
각 구간에 대해 면적 합을 구하고, 모든 구간에 대한 결과를 배열 형태로 반환하여 최종 정답을 도출합니다.
double[] result = new double[ranges.length]; // 결과 배열 생성
for (int i = 0; i < ranges.length; i++) {
int start = ranges[i][0];
int end = n + ranges[i][1];
result[i] = sumAreas(start, end, areas); // 각 구간에 대한 정적분 계산
}
return result; // 결과 배열 반환
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
우박수열을 생성하고 각 구간의 면적을 계산하는 과정이 주어진 k
값에 비례하므로, 시간 복잡도는 O(n)입니다. 또한, 각 구간의 면적을 리스트에 저장하기 때문에 공간 복잡도 역시 O(n)입니다.
- Algorithm
- Math