[프로그래머스][C++] 우박수열 정적분

우박수열 정적분

문제 링크

우박수열 정적분

분석

우박수열(Collatz Conjecture)이라는 수열을 생성하고, 이 수열을 기반으로 특정 구간의 정적분값(넓이)을 구하는 문제입니다.

우박수열은 자연수 k에 대해 다음 규칙으로 수열을 생성합니다.

1. k가 1인 경우 종료
2. k가 짝수인 경우 k / 2
3. k가 홀수인 경우 k * 3 + 1

예를 들어, k가 5일 때, [5, 16, 8, 4, 2, 1]이 나옵니다.

좌표 평면 위에 꺾은 선 그래프를 그린다면 우박수열의 각 숫자를 그래프의 y값으로 하고, x값은 인덱스로 0부터 증가하는 값을 사용해 그립니다.
예를 들어, 위에서 구한 우박수열로 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 점을 만들어 꺾은 선 그래프를 그립니다.

이제 정적분(넓이)을 구해야 하는데, 정적분은 우박수열을 하나의 함수처럼 보고, 특정 구간에 대한 면적을 계산하여 구하면 됩니다.
생성된 수열을 x축, 인덱스를 y축으로 생각하고, 수열을 좌표로 나타냅니다.
이 좌표의 점들을 선분으로 연결하면 계단식 곡선이 형성되고, 이 곡선과 x축 사이의 면적을 구하면 됩니다.

정적분의 계산은 사다리꼴 공식을 사용합니다.
두 인접한 점 $(i, v[i])와 $(i + 1, v[i + 1])$ 사이에서, 해당 구간의 $[i, i+1]$의 면적은 다음과 같이 구합니다.
$A_i = \frac{v[i] + v[i + 1]}{2} \times 1$
위의 공식은 (윗변 + 아랫변) * 높이 / 2입니다.
높이는 1로 고정되어 있으므로 (윗변 + 아랫변) / 2로 계산하면 됩니다.

매개변수인 ranges는 ranges[i] = [a, b]라면, x = a 부터 x = b까지의 면적을 구하라는 뜻입니다.
만약, [a, -b]인 경우 이것은 뒤에서부터 b만큼을 뺀 위치까지 계산하라는 의미로, 전체 수열의 길이가 n이라면 [a, n - b]의 구간이 됩니다.
예를 들어, 위에서 구한 우박수열로 좌표를 구해 그래프를 그렸고, 구간이 [1, 3]일 경우 x = 1부터 x = 3까지의 구간으로 [1, 2], [2, 3]인 두 사다리꼴이 생깁니다.
이때 두 사다리꼴의 넓이를 각각 구하면 다음과 같이 계산할 수 있습니다.
$\frac{v[1] + v[2]}{2} \times 1 = \frac{16 + 8}{2} = 12$, $\frac{v[2] + v[3]}{2} \times 1 = \frac{8 + 4}{2} = 6$
이렇게 구한 넓이를 더하면 전체 면적의 넓이를 구할 수 있습니다.
$12 + 6 = 18$

주어진 구간의 시작점이 끝점보다 커서 a > b로 구간이 유효하지 않다면, 해당 정적분의 결과는 -1.0으로 정의합니다.

사다리꼴 공식을 사용하지 않는다면, 사각형 + 삼각형의 넓이 계산으로 면적을 구할 수 있습니다.

풀이

#include <vector>

using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    
    // 우박 수열을 저장할 벡터
    vector<int> collatzSequence;
    // 우박 수열의 시작인 k를 먼저 저장
    collatzSequence.push_back(k);
    // 우박 수열 생성
    while(k != 1)
    {
        // 짝수인 경우
        if (k % 2 == 0)
        {
            k /= 2;
        }
        // 홀수인 경우
        else
        {
            k = k * 3 + 1;
        }
        
        collatzSequence.push_back(k);
    }
    
    // 우박수열의 크기
    int n = collatzSequence.size();

    // 각 수열 구간 간의 넓이(사다리꼴 넓이)를 저장하는 벡터
    vector<double> areas(n - 1);
    
    // 연속된 두 점의 사다리꼴 넓이 계산
    for (int i = 0; i < n - 1; ++i)
    {
        areas[i] = (collatzSequence[i] + collatzSequence[i + 1]) / 2.0;
    }
    
    // 각 구간의 총 넓이를 구한다.
    for (const auto& range : ranges)
    {
        // 시작 인덱스와 끝 인덱스
        // 끝 인덱스는 전체 길이에 range[1]을 더한다.
        int start = range[0];
        int end = (n - 1) + range[1];
        
        // 시작 인덱스가 끝 인덱스보다 커서 유효하지 않은 구간인 경우
        if (start > end)
        {
            answer.push_back(-1.0);
        }
        // 유효한 구간인 경우
        else
        {
            // 현재 구간에 대한 넓이의 누적합을 저장할 변수
            double area = 0;
            for (int i = start; i < end; ++i)
            {
                area += areas[i];
            }
            
            answer.push_back(area);
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(m \times log \ k)$입니다.

• 우박 수열을 생성하는 반복문 $O(log \ k)$
• 사다리꼴 넓이를 구하는 반복문 $O(n - 1) \approx O(log \ k)$
• 각 구간의 총 넓이를 구하는 반복문 $O(m \times n) \approx O(m \times log \ k)$
  • m은 ranges의 수를 의미합니다.
• $O(log \ k) + O(log \ k) + O(m \times log \ k)$

공간 복잡도는 $O(m + log \ k)$입니다.

• 우박 수열을 저장하는 벡터 vector<int> collatzSequence $O(log \ k)$
• 각 수열 구간 간의 넓이(사다리꼴 넓이)를 저장하는 벡터 vector<double> areas $O(log \ k)$
• 정답을 저장하는 벡터 vector<double> answer $O(m)$
• $O(log \ k) + O(log \ k) + O(m)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.15ms, 4.2MB)
테스트 3 〉 통과 (2.79ms, 6.71MB)
테스트 4 〉 통과 (0.39ms, 4.28MB)
테스트 5 〉 통과 (0.19ms, 3.89MB)
테스트 6 〉 통과 (0.71ms, 4.63MB)
테스트 7 〉 통과 (2.62ms, 6.36MB)
테스트 8 〉 통과 (3.13ms, 6.92MB)
테스트 9 〉 통과 (0.07ms, 4.43MB)
테스트 10 〉 통과 (0.93ms, 4.23MB)