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

문제 정보

제목 : 숫자 블록

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 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 함수를 완성해 주세요.

 

제한 사항

• 1 ≤ begin ≤ end ≤ 1,000,000,000
• end - begin ≤ 5,000

입출력 예

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

 

입출력 예 설명

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

※ 공지 - 2019년 4월 07일 테스트케이스가 변경되었습니다.
※ 공지 - 2023년 2월 09일 지문과 테스트 케이스가 수정되었습니다. 기존에 통과되었던 코드가 통과되지 않을 수 있습니다.

---

나의 풀이

예제를 보며 규칙을 찾아보니 각 숫자에 대해 본인을 제외한 약수 중 가장 큰 수라는 것을 찾았습니다. maxBlock()이라는 함수를 정의하여 n이 1이면 0을 return하고, 그 외의 경우엔 2부터 int(√n)+1까지 반복하는 for루프를 이용합니다. 만약 n을 i로 나눈 나머지가 0이고 i가 10⁷보다 작거나 같다면 tmp리스트에 i를 추가합니다. 그리고 만약 n을 i로 나누어서 나온 정수가 10⁷보다 작거나 같고 n//i가 n이 아니라면 tmp에 n//i도 추가합니다. 만약 n이 소수라면 for루프가 실행되는동안 추가되는 수가 없으니 1을 return하고, 그 외에는 tmp의 max값이 return 됩니다.

begin부터 end+1까지 반복하는 for 루프를 이용해 answer리스트에 위의 함수를 이용해 return된 값을 추가하고 반복이 끝나면 answer을 return합니다.

 

 

코드

def solution(begin, end):
    answer = []
    for n in range(begin,end+1):
        answer.append(maxBlock(n))
    return answer
    
    
def maxBlock(n):
    tmp = [1]
    if(n == 1) :
        return 0
    for i in range(2,int(n**(1/2))+1):
        if(n%i == 0 and i <= 10**7) :
            tmp.append(i)
            if(n//i <=10**7 and n//i != n):
                tmp.append(n//i)
    return max(tmp)