[프로그래머스][C++] 억억단을 외우자

억억단을 외우자

문제 링크

억억단을 외우자

분석

정수의 곱셈 행렬에서특정 범위 내에 가장 자주 등장하는 수를 찾는 문제입니다.

행렬은 대칭이며, 값이 중복됩니다.
$2 \times 3 = 6$, $3 \times 2 = 6$

e는 질문에서의 최대 숫자로 상한값을 의미합니다.
starts는 여러 개의 질문으로 이루어진 배열입니다. s는 퀴즈 시작 범위입니다.

[s, e]범위에서 억억단에 가장 많이 등장한 수 중에 가장 작은 수를 찾아 반환해야합니다.

풀이

#include <vector>

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    
    // 각 수에 대해 등장 횟수(약수 개수)를 저장할 벡터
    vector<int> count(e + 1, 0);
    
    // 약수 개수 계산
    // i는 약수, j는 i의 약수를 가지는 수
    for (int i = 1; i <= e; ++i)
    {
        for (int j = i; j <= e; j += i)
        {
            // j는 i의 배수이므로 i는 j의 약수
            ++count[j];
        }
    }
    
    // dp[i + 1]까지 접근하므로 e + 2 크기를 확보합니다.
    vector<int> dp(e + 2);
    // 마지막 값은 자기 자신으로 초기화
    dp[e] = e;
    
    // dp 배열을 역순으로 채웁니다.
    // i를 거꾸로 탐색하면서 i와 dp[i + 1] 중 count가 더 높은 쪽을 선택합니다.
    for (int i = e - 1; i >= 1; --i)
    {
        // count[i] >= count[dp[i + 1]]이면 i가 더 빈도가 높거나 같으므로 선택합니다.
        dp[i] = (count[i] >= count[dp[i + 1]]) ? i : dp[i + 1];
    }
    
    // starts의 각 값 s에 대한 dp 값을 정답으로 추가합니다.
    for (int e : starts)
    {
        answer.push_back(dp[e]);
    }
    
    return answer;
}

약수의 개수를 구해 개수가 가장 많은 수를 찾아 해결해주었습니다.

count[i]는 i의 약수 개수를 의미하며 i가 억억단에서 등장하는 횟수와 같습니다.

dp[i]는 i 이상 e 이하에서 가장 많이 등장한 수를 저장합니다.

예를 들어 e = 8일때, 다음과 같습니다.

i	count[i]	dp[i + 1]	count[dp[i + 1]]	dp[i] 결정
8	4	-	-	8
7	2	8	4	8
6	4	8	4	6
5	2	6	4	6
4	3	6	4	6
3	2	6	4	6
2	2	6	4	6
1	1	6	4	6

즉, 다시 정리하면 다음과 같습니다.

count = { 0, 1, 2, 2, 3, 2, 4, 2, 4 }
dp = { 0, 6, 6, 6, 6, 6, 6, 8, 8 }

성능 요약

시간 복잡도는 $O(e \ log \ e + n)$입니다.

• 약수 개수를 계산하는 반복문 $O(e \ log \ e)$
• dp 배열을 역순으로 채우는 반복문 $O(e)$
• 쿼리 처리를 하는 반복문 $O(n)$
  • n은 starts의 길이를 의미합니다.
• $O(e \ log \ e) + O(e) + O(n)$

공간 복잡도는 $O(e + n)$입니다.

• 약수 개수를 저장하는 벡터 vector<int> count $O(e)$
• 약수 개수가 가장 많은 수를 저장하는 벡터 vector<int> dp $O(e)$
• 정답을 저장하는 벡터 vector<int> answer $O(n)$
• $O(e) + O(e) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.19MB)
테스트 3 〉 통과 (0.01ms, 4.19MB)
테스트 4 〉 통과 (0.02ms, 4.13MB)
테스트 5 〉 통과 (0.05ms, 4.22MB)
테스트 6 〉 통과 (0.18ms, 4.21MB)
테스트 7 〉 통과 (0.28ms, 3.86MB)
테스트 8 〉 통과 (1.91ms, 4.38MB)
테스트 9 〉 통과 (43.97ms, 16.3MB)
테스트 10 〉 통과 (269.61ms, 47.9MB)