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

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 억억단은 1억 x 1억 크기의 행렬입니다.

- 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
- 수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다.

 

- 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다.

- 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.

 

[문제 조건]

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e,100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복되는 원소가 존재하지 않습니다.

 

[문제 풀이]

이 문제의 핵심은 2가지다.

 

하나는 "약수의 개수를 구하는 것" 그리고 "주어지는 구간에서 약수의 개수가 가장많으면서 작은 수를 빠르게 구하는 것" 이렇게 두가지이다.

 

첫 번째 "약수의 개수를 구하는 것" 부터 살펴보도록 하자.

 

왜 이 문제가 약수의 개수를 구해야 하는 문제일까? 한 번 그림으로 나타내보자

주어지는 조건에 따라 값을 두 수의 곱으로 표현해 보았다. 빈칸은 반대쪽과 순서만 바뀐 값이기 때문에 생략했다.

 

여기서 값이 6인 경우를 주황색으로 색칠해보면

반대쪽도 마찬가지로 (3x2)와 (6x1) 부분이 색칠돼서 총 4개의 칸이 색칠 될 것이다.

이 칸들을 자세히보면 (1x6), (2x3), (3x2), (6x1) 모두 6의 약수의 곱들로 이루어져 있는 것을 확인 할 수 있다.

따라서 억억단 표에서 n이 나오는 횟수는 n의 약수의 개수와 동일하다고 볼 수 있다.

 

void counting(vector<int> &count, int e)
{
    for(int i=1; i<=e; i++)
    {
        if(i*2>e) {count[i]++; continue; }
        
        for(int j=i; j<=e; j=j+i)
            count[j]++;
    }
}

필자는 위 함수를 이용해 매개변수로 들어오는 e까지 모든 수의 약수의 개수를 구하였다.

 

다음으로는 "주어지는 구간에서 약수의 개수가 가장많으면서 작은 수를 빠르게 구하는 것" 를 해결해보자.

 

처음에는 필자는 위에서 만들어진 count배열 순차적으로 starts 배열에서 주어지는 범위를 순차적으로 확인하면서 코드를 작성했는데 ({1,3,7}의 경우 (1~8), (3~8), (7~8) 의 경우를 모두 확인) 이 방법은 당연하게도 시간초과가 발생한다.

 

그래서 max_index라는 배열을 새로만들어 max_index[i]의 값은 다음과 같이 정의했다.

• max_index[i] = i부터 e까지 약수의 개수만 가장많으면서 인덱스가 작은 값

이때 max_index배열을 채울 때 1부터 e까지 오름차순 순서대로 채우는 것이 아니라 e부터 1까지 내림차순 순서대로 채워야 정확하게 채워진다.

 

[소스 코드]

#include <string>
#include <iostream>
#include <vector>

using namespace std;

void counting(vector<int> &count, int e)
{
    for(int i=1; i<=e; i++)
    {
        if(i*2>e) {count[i]++; continue; }
        
        for(int j=i; j<=e; j=j+i)
            count[j]++;
    }
}

vector<int> solution(int e, vector<int> starts) {
    vector<int> answer;
    vector<int> count(e+1, 0);
    vector<int> max_index(e+1, 0);
    
    counting(count, e);

    for(int i=e; i>=1;i--)
    {
        if(i==e) { max_index[i] = e; continue; }
        
        if(count[i] >= count[max_index[i+1]]) 
            max_index[i] = i;    
        else
            max_index[i] = max_index[i+1];
    }
    
    for(int i=0; i<starts.size(); i++)
        answer.push_back(max_index[starts[i]]);   
    
    return answer;
}

굳