[프로그래머스] Lv 2. 숫자블록(Python)

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

 

문제

숫자 블록의 규칙은 다음과 같습니다.

 

1. 블록의 번호가 n일 때, 가장 처음 블록은 n*2번째 위치에 설치합니다.

그 다음은 n*3, n*4, ...로 진행합니다.

2. 만약 기존에 블록이 깔려있는 자리라면 그 블록을 빼고 새로운 블록으로 집어넣습니다.

 

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

특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.

 

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

 

풀이

문제를 읽어보면 결국 n 칸에는 n의 최대 약수가 들어가는 것을 알 수 있습니다.

따라서 begin부터 end까지의 숫자를 하나씩 계산하면서 최대 약수를 구하면 됩니다.

하지만 처음에는 효율성 문제를 통과할 수 있나 고민했지만, 다른 분들의 풀이를 보니 하나씩 구해보아도 통과할 수 있다고 합니다.😆👍

 

먼저 최대 약수를 구하는 함수를 작성해보겠습니다.

1. 숫자가 1일 때는 반드시 0을 반환해줍니다.

if num == 1:
	return 0

 

2. 2부터 sqrt(num)까지의 숫자를 하나씩 나눠보면서 나머지가 0인 경우, 해당 값을 반환해줍니다.

🌹 sqrt(num) ~ 2가 아닌, 2~sqrt(num)인 반복문을 수행하는 것에 주의하세요. 반환 값은 num // i입니다.

end = int(math.sqrt(num))
for i in ragne(2, end+2):
	if num % i == 0:
    	return num // i

여기서 반환되지 않는 수는 1과 자신만을 약수로 가지는 소수입니다.

따라서 이 때는 1을 반환해주도록 하겠습니다.

 

모든 코드를 합치면 아래와 같습니다.

def blockNum(num):
	if num == 1:
    	return 0
        
    end = int(math.sqrt(num))
    for i in range(2, end+2):
    	if num % i == 0:
        	return num // i
    return 1

 

하지만 여기서 문제가 있습니다. 타일은 10,000,000까지만 설치하였지만 주어지는 매개변수는 10,000,000보다 클 수 있다는 점입니다.

때문에 추가적인 조건문이 필요합니다.

 

최소 약수가 10,000,000보다 큰 경우에는 1을 반환할 수 있도록 해주어야 합니다.

 

최소 약수가 10,000,000보다 큰 경우는 1로만 설치가 되어있기 때문입니다.

최종 코드는 아래와 같습니다.

def blockNum(num):
    if num == 1:
        return 0
    
    end = int(math.sqrt(num))
    for i in range(2, end+2):
        if num % i == 0:
            return num // i
        
    return 1

 

코드

import math

def solution(begin, end):
    answer = []
    for i in range(begin, end+1):
        answer.append(blockNum(i))
    return answer

def blockNum(num):
    if num == 1:
        return 0
    
    end = int(math.sqrt(num))
    for i in range(2, end+2):
        if num % i == 0:
            return num // i
        
    return 1