[프로그래머스/C++] 숫자 블록

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 숫자 블록

숫자 블록

문제

그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.

블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, ...로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.

예를 들어 1번 블록은 2,3,4,5, ... 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, ... 인 위치에 설치하고, 3번 블록은 6,9,12... 인 위치에 설치합니다.

이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.

 

제한사항

• begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
• end - begin 의 값은 항상 10,000을 넘지 않습니다.

 

풀이

입출력 예시

 

풀이

처음에 0으로 배열을 초기화한 뒤, 단계를 거쳐가며 수를 바꿔준다면 시간 초과로 실패하게된다. 그래서 규칙을 찾아서 규칙에 맞게 풀이해야 통과할 수 있다.

 

1. 약수를 찾는 방법을 통해서 약수를 찾아준다.

2. 약수 중에서 가장 작은 약수를 이용해 수를 나눈다.

( 만약 그 약수를 나눴을 때 10,000,000을 초과하면 다른 약수를 찾아야 한다. *문제 조건 : 블록 번호는 최대 10,000,000)

3. 그 수를 배열에 추가한다. ( 만약 그 수가 소수였다면 1을 추가 )

 

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;

    for (long long i = begin; i <= end; i++) {
        if (i == 1) {
            answer.push_back(0);
            continue;
        }
        long long n = 1;
        for (long long j = 2; j <= sqrt(i); j++) {
            if (i % j == 0 && i / j <= 10000000) {
                n = j;
                break;
            }
        }
        
        if (n == 1) {
            answer.push_back(1);
        }
        else {
            answer.push_back(i / n);
        }
    }
    
    return answer;
}