title: "[프로그래머스] 억억단을 외우자 C++ 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/138475"
description: "프로그래머스 Level 3 문제 [억억단을 외우자]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

#include <string>
#include <string.h>
#include <vector>

using namespace std;

int A[5000001];
int B[5000001];

vector<int> solution(int e, vector<int> starts) {
    memset(A, 0, sizeof(int));
    memset(B, 0, sizeof(int));
    
    for (int i = 1; i <= e; i++) {
        int n = i;
        while (n <= e) {
            A[n]++;
            n += i;
        }
    }
    // B[i]는 i부터 e까지 중 A[i]가 가장 큰 i값을 저장합니다.
    B[e] = e;
    for (int i = e-1; i > 0; --i) {
        if (A[i] >= A[B[i+1]]) {
            B[i] = i;
        } else {
            B[i] = B[i+1];
        }
    }
    
    vector<int> answer;
    for (int s: starts) {
        answer.push_back(B[s]);
    }
    return answer;
}

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges