[BOJ] 2501. 약수 구하기

2501번: 약수 구하기

 

✍️ 문제 요약

두 자연수 N과 K가 주어졌을 때 N의 약수들 중 K번째로 작은 수를 출력하라.

 

💪 무식하게 풀기

우선 말그대로 K번째 약수를 구해야겠다는 생각이 가장 먼저 떠올랐다.

 

K번째 약수는 어떻게 구할 수 있을까❓

cnt 변수를 활용하여 구할 수 있다.

 

1부터 N까지 i로 순회하면서 N을 i로 나눈 몫이 0이라면 i는 N의 약수인 것이다. 이때 cnt를 1 증가한다.

이를 반복하여 K번째 약수를 구한다.

 

만약 K번째 약수가 있다면 출력 후 break로 반복문을 빠져나가고, 끝까지 반복문을 빠져나가지 못한다면 else 문에서 0을 출력한다.

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

cnt = 0
for i in range(1, N+1):
    if N % i == 0:
        cnt += 1
        if cnt == K:
            print(i)
            break
else:
    print('0')

이 코드의 시간 복잡도는 O(n)이다.

 

🎯 최적화

성능적인 측면에서 최적화가 도저히 떠오르지 않아 아쉬운대로 기존 코드를 예쁘게(?) 변경해봤다.

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

cnt = 0
for i in range(1, N+1):
    if N % i != 0: # i가 N의 약수가 아니라면 넘어가기
        continue
    cnt += 1
    if cnt == K:
        print(i)
        break
else:
    print('0')

 

🤔 다른 사람의 코드를 탐구해보기

약수만 추출한 리스트에 [0]*10000 을 이어붙인다.

N의 범위가 10000 이하니까 약수의 개수가 K보다 작았을 때 0이 출력될 수 있도록❗️

 

완성된 리스트의 K-1번째 원소를 출력한다.

N, K = map(int, input().split())
print(([i for i in range(1, N+1) if N % i == 0] + [0] * 10000)[K-1])

굉장히 파이써닉한 코드같다.

약수만 추출할 생각은 했는데, 그 뒤에 [0]*10000 을 이어붙여 약수가 K개 이하일 때 0이 출력될 수 있도록 한 발상이 새로웠다. 😲

 

위 코드의 시간 복잡도는 O(n)이다.