Programmers - 숫자 블록

---

title: Programmers - 숫자 블록
date: 2022-07-16
tags:

• Algorithm

---

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

문제 요약

1부터 1e7까지의 숫자 블록이 있다. 이 블록들은 1의 배수를 제외한 자연수 배수 위치에 설치한다.
작은 숫자의 블록 먼저 설치하며, 큰 숫자의 블록이 이미 존재하는 곳에 설치하려고 하면 큰 숫자의 블록으로 설치한다.
최대 1e9까지의 범위가 주어질 때, 주어진 구간의 숫자 블록의 설치 번호를 vector에 넣어 return한다.

문제 풀이

문제를 잘못 이해하여 삽질을 하였다.
블록을 까는 방식이 소수를 걸러내는 방식과 유사하여 소수를 이용한 문제로 착각하여 잘못 풀었다.

3e8의 경우 30 * 1e7이 되므로 해당 위치에는 1e7 블록이 설치된다.
결국 n번 위치에 들어가는 숫자 블록은 n의 약수 중 1e7 이하의 최대 약수이다.
이를 소인수분해 하여 계산하기에는 알고리즘이 복잡해지며, 이로 인하여 더 오랜 시간이 걸릴 수도 있다.
무식하게 확인하는 것이 최적이라고 판단하여 Bruteforce 방식으로 풀었다.

2부터 수를 증가해가며, 이 수로 나누어 1e7 이하의 몫으로 나누어 떨어지는지 확인한다.
이러한 조건이 충족하면 가장 먼저 발견한 값이 그 위치의 숫자 블록이며, 어떠한 값도 발견하지 못한다면 1번 블록만 들어갈 수 있다.

무식하게 순회를 하여 최대 약 128ms의 시간이 소모되었다.
더 효율적인 프로그램을 작성하기 위해서는 몫을 찾는 더욱 좋은 알고리즘을 사용해야 한다.

프로그램

#include <vector>
#include <cmath>

using std :: vector ;

vector < int > solution ( long long begin , long long end )
{
    vector < int > answer ( end - begin + 1 , 0 ) ;
    int * ipAnswer = answer.data () ;
    int iPrimeSize = 1 ;



    for ( int i = begin ; i <= end ; ++i )
    {
        if ( 1 == i )
        {
            ipAnswer [ 0 ] = 0 ;

            continue ;
        }

        ipAnswer [ i - begin ] = 1 ;

        for ( int j = 2 ; j * j <= i ; ++j )
        {
            if ( ( 0 == i % j ) && ( i / j <= 10000000 ) )
            {
                ipAnswer [ i - begin ] = i / j ;

                break ;
            }
        } 
    }


    return answer ;
}