[Algorithm] 기초 문제 / K번째 약수

▶ 문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.
6의 약수는 1, 2, 3, 6, 총 네 개이다. 두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

▶ 입력 설명

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

▶ 출력 설명

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

▶ 입력

6 3

▶ 출력

3

---

 

▷ 내가 짜본 코드

import sys
sys.stdin = open('input.txt', 'rt')
n, k = map(int, input().split())

a = []

for i in range(1, n+1):
    if n % i == 0:
        a.append(i)
if len(a) < k:
    print(-1)
else:
    print(a[k-1])

k번째 작은 수를 구해야 하기 때문에 index를 활용해야 한다고 생각했다.
그러기 위해서 약수들을 배열에 넣어 저장한 후 [k-1] index를 출력했다.

 

b = [i for i in range(1, n+1) if n % i == 0]
if len(b) < k:
    print(-1)
else:
    print((b[k-1]))

최근에 배운 반복문 간소화 문법으로 이렇게 한줄로 줄이는 것도 연습해 봤다.
한 줄로 코드가 정리되는 걸 보니 신기하다....

 

▷ 예시 코드

cnt=0
for i in range(1, n+1):
    if n%i==0:
        cnt+=1
    if cnt==k:
        print(i)
        break
else:
    print(-1)

예시 코드에서는 숫자를 다른 데이터 타입으로 바꾸지 않고 그대로 사용하였다.
약수의 개수 자체를 counting 해서 쌓은 후에, k번째 counting한 값을 바로 출력하는 방식이다.
k번째 값을 찾으면 조건문과 반복문을 끝내고, k값을 찾지 못한다면 -1을 출력한다.

혼자 생각하기는 어려운 방법이라 계속 곱씹어 보게 된다.