개발/알고리즘

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

개발자_티모 2023. 5. 21. 01:43
반응형

문제 이해하기

숫자 0이 적힌 블록들에 다른 숫자가 적힌 블록들을 설치하려고 한다. 블록을 설치하는 규칙은 다음과 같습니다

블록에 적힌 번호가 n 일 때 가장 첫 블록은 n * 2번 째 도로의 위치에 설치, 그 다음은 n * 3, 4 ...도로의 위치에 설치합니다.

이 때 기존에 설치된 블럭이 존재한다면 해당 블록을 빼고 새로운 블록을 설치합니다.

 

각 블록은 오름차순으로 주어집니다. 또한 블럭의 숫자는 1 ~ 10,000,000까지의 숫자만 존재합니다.

문제 해결 방법

1. 도로의 입장에서 생각해보면 도로에 설치될 수 있는 블럭은 도로의 위치의 약수입니다.

  예를 들면 10번 도로의 위치에는 1, 2, 5의 블록이 설치될 수 있다. 10의 블록이 설치될 수 없는 이유는 10(도로)은 10(블럭) * 1이기 때문에 문제의 조건에 위반됩니다.

 

2. 약수를 빠르게 계산할 수 있어야 합니다.

 약수의 정의를 보면 N / A의 나머지가 0이 된다면 그 몫도 약수가 됩니다. 즉 대칭적인 성질을 가지고 있습니다. 따라서 SQRT를 사용하면 대칭의 마지막 지점을 구할 수 있게 됩니다.
 예를들면 SQRT(36)을 진행하게 된다면 6이 되고, 36의 약수의 대칭 지점이 6입니다. 따라서 기존의 N까지의 모든 약수를 구하는 방식보다 더 빠르게 문제를 해결할 수 있습니다.

코드

import math

def find_largest_proper_divisor(n):
    if n == 1:
        return 0
    
    answer = 1
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if 10000000 < int(n / i):
                answer = max(answer, i)
            else:
                answer = max(answer, int(n/i))
    
    return answer

def solution(begin, end):
    answer = []
    
    while begin <= end:
        answer.append(find_largest_proper_divisor(begin))
        begin += 1
        
    return answer

if __name__ == "__main__":
    begin = 100000014
    end = 100000016
    print(solution(begin=begin, end=end))

 

코드 리뷰

 

배운점 정리하기

이번 코드 리뷰를 통해 배운 점은 다음과 같습니다.

 

문제를 꼼꼼하게 읽는 것이 매우 중요하다.사용할 수 있는 블록은 1에서 10^7까지인데 초기에는 이 구문을 못보고 왜 틀렸지했습니다.
앞으로는 문제를 보다 꼼꼼하게 읽어야겠다

반응형