코딩테스트 -- 숫자 블록 - (프로그래머스 / C++)

https://school.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을 넘지 않습니다.

 

---

요약하면

숫자 블록들을 순서대로 배수에 채워 넣는데 만약 이미 블록이 있다면? 바로 교체해주며 끝까지 채우는 문제입니다!

 

 

문제 자체는 간단했습니다.

만약 문제처럼 되면 항상 현재 블록에는 현재 블록번호의  최대 공약수블록이 넣어지게됩니다!

 

 

그래서 최대공약수를 찾도록하는 방법으로 접근했습니다.

 

 

시작!

 

---

먼저 저장해줄 배열을 만들어 주고

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    answer.resize(end-begin+1,0);

 

탐색해 줍시다.

여기서는 조금 생각해서 풀어 보았는데요

 

만약 10 이있다면 공약수를 찾기위해  2 3 4 5 이런식으로 찾아 갈것입니다.

 

그러기 전에 최소 공약수를 찾는다면? 바로 2를 찾게되는 순간 10/2 를 통해 5라는 최대공약수를 찾아낼수있습니다!

현재 숫자에서 최소공약수를 나눈값 = 최대 공약수가 되게됩니다!!!

 

이 방법을 통해 좀더 빠르게 푼것 같습니다. >> 뒤에서부터 탐색해도 똑같을것 같네요;;

 

그리고 + 최대공약수는 현재 넘버의 제곱근보다 항상 작거나 같은 점을 꼭 이용해주셔야 합니다! (이거 놓치면 시간초과)

for(int i=begin;i<=end;++i){
        int num=0;
        
        for(int j=2;j<=sqrt(i);++j){
            
            if(i%j==0 && i/j<=10000000){
                answer[i-begin]=i/j;
                break;
            }
        }
        if(answer[i-begin]==0){
            answer[i-begin]=1;
        }
    }

 

그리고 소수들도 처리해주고

if(answer[i-begin]==0){
            answer[i-begin]=1;
        }

 

1자리에는 0을 채워줍시다!

    if(begin==1){
        answer[0]=0;
    }

 

여기까지 함정을 피하셨다면 끝!

 

 

 

*ALL

#include <string>
#include <vector>
#include<iostream>
#include <cmath>
using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    answer.resize(end-begin+1,0);
    
    for(int i=begin;i<=end;++i){
        int num=0;
        
        for(int j=2;j<=sqrt(i);++j){
            
            if(i%j==0 && i/j<=10000000){
                answer[i-begin]=i/j;
                break;
            }
        }
        if(answer[i-begin]==0){
            answer[i-begin]=1;
        }
    }
    
    if(begin==1){
        answer[0]=0;
    }
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!