📑 문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/12923#
🔥 문제 설명
숫자 블록을 설치하는데 주어진 begin, end 두 변수 사이 구간만큼 설치한다. 이때, 1블록은 n*1에 해당하는 곳, 2블록은 n*2에 해당하는 곳에 위치하도록 한다. 즉, n블록은 k*n에 위치하도록 해야한다. 만일, 이미 다른 블록이 있다면 그 블록을 새 블록으로 변경해야 한다. 이때, n블록의 길이는 1부터 10,000,000블록까지 존재하고 설치하려는 구간은 1부터 1,000,000,000까지 존재한다.
🔥 나의 풀이
나의 풀이라고 하지만, 도저히 혼자 풀 수 없어 도움을 받았다. 이 문제는 약수를 구하는 문제와 동일하였다.
(n=10일때) 2번 블록을 설치하려고 한다고 해보자.
4번 블록, 6번 블록 8번 블록, 10번 블록이 각각 4, 6, 8, 10으로 변한다. 이는 곧, 2*2, 2*3, 2*4, 2*5라고 표현할 수 있다.
이때 각 숫자의 약수를 표현해보면 4 = {1,2,4} / 6 = {1,2,3,6} / 8 = {1,2,4,8} / 10 = {1,2,5,10}이다. 2가 약수로 들어있는 모든 수가 2번 블록으로 변하였다. 이는 다시말하자면 약수중, 자기 자신 숫자를 제외한 수로 계속 변하게 된다는 말이다.
따라서 약수를 오름차순으로 정렬하였을 때, 자기자신을 제외한 가장 큰 약수가 최종 블록이 된다. 가장 큰 약수는 곧, 가장 작은 약수로 나누었을때의 몫이 된다. 이를 바탕으로 한 나의 풀이는 아래와 같다.
def solution(begin, end):
answer = []
for i in range(begin,end+1):
if (i==1):
answer.append(0)
continue
for j in range(2,int(i**(1/2))+1):
if (i)%j ==0:
if i//j > 10**7:
continue
answer.append(i//j)
break
else: #break가 안되었다면 실행
answer.append(1)
return answer i가 1인경우를 제외하고 반복문을 돌면서 약수를 구할 때 가장 먼저 나누어 떨어지는 경우(=가장 작은수로 나누어 떨어지는 경우)의 몫을 answer에 넣고 바로 break를 하도록 하였다.
이때 10**7이 넘어가는 경우 answer에 넣어주지 않는 부분이 존재하는데, 이부분이 효율성 체크에서 가장 힘들었던 부분이다. 효율성체크가 시간초과가 아닌 "실패"가 뜨는데 이는, 블록이 10**7까지밖에 존재하지 않기 때문이다. answer에는 블록의 종류를 넣어줘야 한다. 하지만 블록이 10**7까지밖에 없지만, end의 범위는 10**10까지 이므로 10**7보다 더 큰 몫이 발생하게 된다. 따라서 이경우에는 10**7이상의 값이 들어갈 수 없도록 하였다.
📍 for - else문
python에만 있는 문법으로(확실치는 않다...)일반적인 if - else문에서 사용되는 else와 비슷하게 사용된다.
for문이 중간에 break를 만나 끝나지 않고, 끝까지 다 완료되었다면 실행하라는 구문이다.
잊어먹을때 쯤 다시한번 꼭 풀어봐야 겠다..
