[프로그래머스 스쿨][Python] 숫자 블록 (조건 이상)

문제

문제 설명

그렙시에는 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을 넘지 않습니다.

입출력 예시

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

예시) 깔린 블록

문제: 프로그래머스 스쿨 - 연습문제 - 숫자 블록

 

---

문제 풀이

유의사항

• 특정 수의 약수를 검사하는 알고리즘은 O(√N)이다.
• 소수를 검사하는데에 효율적으로 사용할 수 있는 알고리즘인 '에라토스테네스의 체'라는 알고리즘이 있다.
  (다만 이 문제에는 사용되지 않는다.)
• 문제가 이상하다.
  • 길이가 10^9인 도로에, 10^7번까지의 블록을 놓았댄다. 이를 초과하는 범위의 수는 1로 초기화해야 한다.
    (놓지 않았으면 0이여야 하는게 아닌가... 근데 그렇게 하면 효율성 테스트를 통과하지 못한다.)
  • 애초에 도로의 길이와 블록을 놓은 곳의 길이가 왜 다른것인지 모르겠다. 
  • 이에 대한 언급이 문제에 아예 없다.

풀이

• 핵심 아이디어: (가장 마지막으로 놓인 블록) = (가장 큰 진약수) 라는 점에 주목하자.

    ※ 진약수: 자기 자신을 제외한 양의 약수

---

전체 코드

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

def findLargestDivisor(n):
    if n == 1:
        return 0
    
    for i in range(2, int(n ** (1/2)) + 1 ):
        if n % i == 0:
            if n//i > 10 ** 7: # 문제에서 가장 이해할 수 없는 부분
                continue
            else:
                return n//i # (n을 '가장 작은 약수'로 나눈 수) = (가장 큰 약수)
    return 1