(인프런) 파이썬 알고리즘 문제1-1 "K번째 약수"

python

Problem

K번째 약수 어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.

6을 예로 들면 6 ÷ 1 = 6 … 0 6 ÷ 2 = 3 … 0 6 ÷ 3 = 2 … 0 6 ÷ 4 = 1 … 2 6 ÷ 5 = 1 … 1 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

 

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

 

▣ 입력설명

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

 

▣ 출력설명

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다.

만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 -1을 출력하시오.

 

▣ 입력예제

6 3

▣ 출력예제

3

 

---

💯 Solution ① 

: Before Lecture (Only My Thinking)

# 파일에서 값을 가져옴
import sys
# 채점을 할 때는 아래 코드 주석 처리
sys.stdin=open("input.txt", "rt")
 
# input.txt를 map()을 통해서 가져와서 split()으로 나눠서 N, K에 배정한다.
N, K=map(int, input().split())
divisor_array = []
 
def divisor(N,K):
    for i in range(1,N+1):
        if N%i==0:
            divisor_array.append(i)
    if len(divisor_array) >= K:
        print(divisor_array[K-1])
    else:
        print(-1)
 
 
divisor(N,K)
 
 

- divisor_array 라는 배열을 사용 (해당 배열에는 약수가 들어갈 예정)

- for in문을 통해서 약수를 구하고 해당 수를 divisor_array에 append

- 배열의 길이가 K보다 클 때, 해당 배열의 K번째를 뽑음 (인덱스로 하면, K-1)

- K가 배열의 길이보다 더 크다면, '-1'을 출력

 

💯 Solution ②

: After Lecture (Tutor Advice)

# 파일에서 값을 가져옴
import sys
# 채점을 할 때는 아래 코드 주석 처리
sys.stdin=open("input.txt", "rt")
 
# input.txt를 map()을 통해서 가져와서 split()으로 나눠서 N, K에 배정한다.
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
# 정상적으로 for문이 끝나면 (break를 당하지 않은 것 = K만큼 cnt가 없음)
else:
    print(-1)
 

- for ~ in 문과 else문을 사용

- cnt : 약수의 갯수를 세주는 변수를 사용