Programmers / 숫자 블록 / Python 파이썬

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 숫자 블록(2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12923

• 숫자 블록

문제 설명

그렙시에는 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]

입출력 예 설명

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

※ 공지 - 2019년 4월 07일 테스트케이스가 변경되었습니다.

---

나의 풀이

 

각각의 숫자에 대해 최대 약수를 찾으면 되는 문제이다.

 

def yaksu(n):
    for i in range(n//2,0,-1):
        if n % i == 0:
            return i
        

def solution(begin, end):
    # 규칙
    # 각 숫자의 최대 약수가 들어가야함
    # 최대 약수를 구하는 알고리즘
    answer = []
    for i in range(begin,end+1):
        if i == 1:
            answer.append(int(0))
        else:
            answer.append(yaksu(i))
    return answer

풀이는 맞는데 왜 효율성에서 실패를 하는거지..

 

조건에 블록의 번호는 10,000,000까지만 사용한다는 내용이 중요하기 때문!!

 

자기자신을 제외한 최대 약수가 10,000,000을 넘는다면,
해당 블럭은 사용하면 안되는 블럭이다.

그러므로 해당경우에는 그 다음으로 큰 최대 약수를 다시 찾아 블록을 끼워넣어주면 된다.

 

def yaksu(n):
    for i in range(n//2,0,-1):
        if n % i == 0 and i <= 10000000:
            return i
    return 1
        

def solution(begin, end):
    # 규칙
    # 각 숫자의 최대 약수가 들어가야함
    # 최대 약수를 구하는 알고리즘
    answer = []
    for i in range(begin,end+1):
        if i == 1:
            answer.append(int(0))
        else:
            answer.append(yaksu(i))
    return answer

2차 수정해도 효율성이 풀리지 않았다 ㅠㅠ

그래서 약수를 다르게 구하도록 해보았다.

 

수정한 약수 식

def yaksu(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if (n // i) <= 10000000:
                return n // i
            
    return 1

제곱근을 이용해서 범위를 줄이고 구해나가면 약수를 구하는 계산이 빨라진다.

 

모범답안

def yaksu(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if (n // i) <= 10000000:
                return n // i
            
    return 1
                
        
        

def solution(begin, end):
    # 규칙
    # 각 숫자의 최대 약수가 들어가야함
    # 최대 약수를 구하는 알고리즘
    answer = []
    for i in range(begin,end+1):
        if i == 1:
            answer.append(int(0))
        else:
            answer.append(yaksu(i))
        
    return answer

성공!!

---

※ 알아야 할 것

- 제곱근을 이용해서 범위를 줄이고 구해나가면 약수를 구하는 계산이 빨라진다.