[백준/Python] 2501번 약수 구하기 문제

■ 2501번 약수 구하기 문제

 

출처: 백준 2501번 약수 구하기 문제

 

■ 코드 풀이

 

두 가지 풀이법을 공유드리겠습니다. 처음 제가 푼 코드와 업그레이드한 코드입니다. 먼저 아래는 기본적으로 누구나 생각할 수 있는 코드입니다. 아래 코드는 N이 10,000 이하의 수여서 최대 10,000번의 for문을 실행할 수 있습니다. 제출할 때는 실패할까 봐 조마조마했지만, 다행히 정답처리 된 코드입니다.  

N, K = map(int, input().split())

num_list = []

for i in range(1,N+1):
    if N % i == 0:
        num_list.append(i)

if K > len(num_list):
    print(0)
    
else:
    print(num_list[K-1])

 

그렇지만, 약수의 속성을 잘 안다면 코드를 더 단축할 수 있습니다. 기본적으로 어떤 숫자이든, 1과 자기 자신을 약수로 갖습니다. 다시 말하면, 자기 자신을 제외하고 가장 큰 값은 자기 자신을 2로 나눈 값입니다. 그래서 for loop의 범위를 아래와 같이 변경할 수 있습니다. 이렇게 하면 코드 실행 시간이 약 10% 정도 개선되네요. 

N, K = map(int, input().split())

num_list = []

for i in range(1,N//2+1):
    if N % i == 0:
        num_list.append(i)
        
num_list.append(N)

if K > len(num_list):
    print(0)
    
else:
    print(num_list[K-1])