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

문제주소 :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일 테스트케이스가 변경되었습니다.

 

<풀이법>

▒ 한줄 개념: 약수 계산 ▒ 

생각보다 풀이가 복잡하지는 않은 문제입니다. 물론 고생은 좀 했지만..

쉽게 얘기해서, 각 숫자(n)의 블록값은 (n // 1이 아닌 가장 작은 약수) 가 됩니다.

블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, ...로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.
예를 들어 1번 블록은 2,3,4,5, ... 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, ... 인 위치에 설치하고, 3번 블록은 6,9,12... 인 위치에 설치합니다.

위 예시를 보면, 어떤 n번 블록은 해당 n을 나누어 떨어지게 할 수 있는 값 중 가장 큰 값임을 알 수 있습니다.

약수값 중 가장 큰 값이라는 것은, 반대로 생각하면 가장 작은 약수값으로 n을 나누었을 때의 몫이 되는 것입니다.

2: 2 // 2 = 1

3: 3 // 3 = 1

4: 4 // 2 = 2

5: 5 // 5 = 1

6: 6 // 2 = 3

7: 7 // 7 = 1

8: 8 // 2 = 4

9: 9 // 3 = 3

10: 10 // 2 = 5

 

따라서 위와 같은 방식으로 코드를 구현해주면, 정확성은 쉽게 풀 수 있습니다.

다만 효율성에서는 다 틀릴 수 있는데, 여기서 하나의 주의점이 있습니다.

그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

도로의 길이는 최대 십억(1,000,000,000)인 반면에, 블록의 최댓값이 천만(10,000,000)이라는 것입니다. 

따라서 천만 이상의 블록값은 가질 수 없으므로, 위의 나누기 과정에서 몫이 천만 이상일 경우 조건문을 통해 패스해주어야 합니다.

예시로, 도로값이 십억(1,000,000,000)일때, 가장 작은 약수로 나눈 값은 오천만(50,000,000)이지만, 이 값은 최대 블록값을 초과하므로, 적절한 값이 될 수 없게 됩니다.

 

<코드(Python)>

def solution(begin, end):
    answer = []
    MAX = 10000000
    for num in range(begin, end + 1):
        if num == 1:
            answer.append(0)
            continue
        else:
            start = 2 if num % 2 == 0 else 3
            answer.append(1)
            for i in range(start, int(num ** 0.5) + 1):
                if num != i and num % i == 0:
                    if num // i <= MAX:
                        answer[-1] = num // i
                        break
    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest