프로그래머스] C++ 숫자 블록(Level 4)

 

 

 

 

 

해당 문제는 프로그래머스에서 푸실 수 있습니다.

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

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

 

 

 

1. 문제

문제 설명

그렙시에는 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을 넘지 않습니다.

 

 

입출력 예

 

begin	end	result
1	10	0, 1, 1, 2, 1, 3, 1, 4, 3, 5

입출력 예 설명

입출력 예 #1
다음과 같이 블럭이 깔리게 됩니다.

 

 

2. 풀이

이 문제는 나눗샘으로 풀 수 있습니다.

 

해당 예제 인덱스를 보면 

2 인덱스 = 1

3 인덱스 = 1

4 인덱스 = 2

5 인덱스 = 1

6 인덱스 = 3

7 인덱스 = 1

8 인덱스 = 4

9 인덱스 = 3

10 인덱스 =5

 

이렇게 되어 있습니다.

 

처음엔 규칙을 찾는게 어렵지만 해당 인덱스 값은 1과 자신을 제외한 최소 약수로 이뤄져있습니다.

 

4 = 1, 2, 4

7 = 1, 7

9 = 1, 3, 9

10 = 1, 2, 5, 10

 

이렇게 되어 있으며 여기서 1과 자신을 제외한 최소 약수로 이뤄지게 됩니다.

 

단, 소수일 경우에는 1로 표시되는걸 알 수 있습니다.

 

따라서 저희는 begin ~ end 값 사이에 있는 것들에 대해 최소 약수와 소수를 판별해 구해주면 됩니다.

 

여기서 효율성 테스트에서 계속 실패했는데, for문안에 if문을 넣거나, long long 타입으로 계산하거나,

 

10,000,000 값일 때 예외처리를 안해서 그렇습니다. 

 

문제를 읽어보시면

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

라는 부분이 있으며, 이를 처리해 줘야 합니다.

 

해당 부분은 블록의 위치, 즉 최소 약수가 10,000,000을 넘으면 안됩니다.

 

때문에 정리하자면 다음과 같이 구해주시면 됩니다.

 

1. begin ~ end 까지에서 최소 약수를 찾아서 넣어준다.

2. 최소 약수를 찾을 때 해당 값이 소수인지 판별해준다.

3. 약수를 찾는 과정에서 최소 약수가 10,000,000을 넘어설 경우 1로 처리해 준다.

 

3. 코드

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

using namespace std;

int check(int n){
    int num = sqrt(n);
    for(int i = 2; i <= num; i++){
        int quo = n / i;
        if(n % i == 0 && n / i <= 10000000)
            return n / i;
    }
    return 1;
}

vector<int> solution(long long begin, long long end) { 
    vector<int> answer;
    
    for(int i = begin; i <= end; i++){
        answer.emplace_back(check(i));
    }
    if(begin == 1) answer[0] = 0;
    return answer;
}