[프로그래머스] - 숫자 블록

문제

---

숫자 블록

 

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

즉, 주어진 범위에서 위치할 수 있는 최대 블록을 각각 구하라 입니다.

주의해야 할점은 길이와 블록의 크기가 상당히 많이 차이납니다.

 

알고리즘

---

해당 문제는 어떤 방식으로 해야 최대 블록을 구할 수 있을까에 대해 접근을 못하면 구현하기가 어려울 수도 있습니다.

결국 현재 위치한 number라고 할 때, 최대 블록을 구하는 방법입니다.

즉, number를 1이 아닌 가장 작은 약수로 나누게 된다면, 구할 수 있는 최대 블록입니다.

 

또한, 길이와 블록 범위가 다르기 때문에 이 부분을 고려하지 않으면 효율성에서 틀립니다.( 왜 효율성에서 틀리게 한지는 모르겠어요.. 정확성에 데이터 추가해야 되는거 아닌가 싶긴합니다. )

 

1. 함수를 이용하여 Number에 대한 최소 약수 구현 ( 단, 블록의 범위를 넘지 않도록 )

2. 만약 Number에 약수가 없다면 현재 본인의 값을 Return ( 계산 용이하도록)

3. 주어진 범위에 대해서 함수에 대해 처리

 

코드

---

# 숫자 블록
import math
def yaksu(num):
    if num == 1:
        return 0
    for i in range(2,int(math.sqrt(num))+1):
        if num//i<10000000 and num%i==0 :
            return i
    return num

def solution(begin, end):
    answer =[]
    for i in range(begin,end+1):
        block=yaksu(i)
        if block==0:
            answer.append(0)
        else:
            answer.append(i//block)
    return answer