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

문제 - 숫자 블록 https://school.programmers.co.kr/learn/courses/30/lessons/12923

프로그래머스

시작하는 (begin) 블록 부터 끝나는 (end) 블록 까지 각각 어떤 수로 구성되어있는지 확인하는 문제다.

예제인 1 ~ 10을 보고 나서 자기 자신을 제외한 공약수 중에서 가장 큰 공약수를 구하면 되겠다고 생각했다.

지점 7의 경우 공약수가 [1, 7] 로 구성되어있고, 이 중 7 은 2의 배수인 14에서 처음 등장할 예정이기 때문에 7을 제외한 1이,

지점 8의 경우, 공약수가 [1, 2, 4, 8] 로 구성되어있고, 위와 같은 이유로 8은 올 수 없으므로 4가 답이 된다.

end - begin 의 값은 최대 5,000으로 완전 탐색(여기서는 2중 for 문)은 불가능하다고 생각했고,

한 번의 순회 + 더 적은 계산으로 찾을 방법을 모색했다.

처음에는 단순히 2 나 3으로 나눠떨어지지 않으면 1로 처리해도 되는건가 생각했다가

제곱수 - 25 [1, 5, 25] / 49 [1, 7 , 49] 의 경우에는 위와 같은 방식으로는 정답을 찾을 수 없기 때문에

"Root 값 까지만 확인하면서 나눠떨어지는 수가 있는지"를 확인하고자 코드를 구성했다.

1. 최초 제출 코드

import math

def root_check(number):
    root = int(math.sqrt(number))
    value = 1
    for r in range(2, root + 1):
        if number % r == 0:
            return number // r
            
    return value

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

root_check 를 보면, 1로 나누면 모든 수의 나머지가 0이 되기 때문에, 2부터 시작해서 탐색 번호의 Root 번호 까지만 순회하며

나누어 떨어진다면 탐색하고자 하는 수를 나눈 몫이 정답이 될 것이라고 생각하고 코드를 구성했다.

결과는 실패, 구현 때 제대로 짚고 넘어가지 않은 부분이 존재했다.

숫자의 번호가 10,000,000를 넘어가지 않는다는 부분과 1 <= begin <= end <= 1,000,000,000 인 부분이다.

즉, end 값이 가장 클 때 (end 가 1,000,000,000 일 때) 마지막 값은 500,000,000이 될 수 없다는 부분이다.

이 부분을 해결하기 위해, 2부터 탐색값의 Root 번호까지 탐색하되 number // r 의 값이 10,000,000을 넘어간다면

r을 value 값과 비교해서 더 큰 수를 갱신하는 방식으로 변경했다.

 

2. 수정 제출 코드

import math

def root_check(number):
    root = int(math.sqrt(number))
    value = 1
    for r in range(2, root + 1):
        if number % r == 0:
            if number // r <= 10000000:
                value = max(value , number // r)
            
            else:
                value = max( value, r)    
    return value

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