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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12923

1. 1 ~ 10**7 의 숫자가 적혀있는 블록들이 있다.

2. 도로의 길이는 10**9이다.

3. 다음과 같이 n번 블록을 n*2, n*3, n*4, ... 위치의 도로에 설치한다.

 

4. 3번 과정을 끝까지 마쳤을 때, begin부터 end까지의 위치에 있는 블록의 숫자를 반환한다.

 

접근

num이 1, 2, 3일 때는 for문이 돌아가지 않기 때문에 0, 1, 1을 따로 answer에 넣어주었다.

 

마지막에 각 num 위치에 남게되는 블록의 숫자는 num의 최대공약수가 된다.

따라서 2부터 int(math.sqrt(num))까지 나눠주며 num이 가장 먼저 나누어 떨어졌을 때의 값을 블록의 숫자로 넣어주었다.

 

→ 여기서 도로의 길이는 10**9인데 블록의 숫자는 10**7까지라는 점을 따져주지 않아서 틀렸다.

import math


def solution(begin, end):
    answer=[]

    for num in range(begin, end + 1):
        if num==1:
            answer.append(0)
            continue
        elif num==2 or num==3:
            answer.append(1)
            continue

        # 나누어 떨어지는 값 중 가장 작은 수로 나눈 값 반환
        breakcheck = 0
        for i in range(2,int(math.sqrt(num))+1):
            if num % i == 0:
                answer.append(num//i)
                breakcheck = 1
                break

        # num이 어떤 i로도 나눠지지 않는다면 1 반환
        if breakcheck == 0:
            answer.append(1)

    return answer

 

제출 코드

num을 2 ~ int(math.sqrt(num))으로 나눴을 때, num // i 또는 i가 10**7이 넘어가면 안된다. 

따라서 num // i 뿐만 아니라 i 도 고려해서 최대값을 찾아줘야한다.

import math


def solution(begin, end):
    answer = []

    for num in range(begin, end + 1):
        tmp = int(num != 1)

        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                if num//i<=10**7:
                    tmp=max(tmp,num//i)
                    break
                if i<=10**7:
                    tmp=max(tmp,i)

        answer.append(tmp)

    return answer

 

 

회고

머리가 안돌아간다. 너무 헷갈렸다.