[BOJ] 2501. 약수 구하기 (Python/Bronze 3)

---

[문제 링크] 👉 https://www.acmicpc.net/problem/2501

---

풀이 방법

약수 구하기

• N의 약수를 모두 찾기 위해 1부터 N의 제곱근 까지의 수 i를 확인한다.
• 만약 i가 N의 약수라면 i 와 N / i 를 약수 리스트에 추가한다. 이때, i와 N / i 가 같지 않으면 중복을 피하기 위해 둘 다 추가한다.
  • 예를 들어 N이 36일 때, 약수로 6이 두 번 나올 수 있기 때문이다.

정렬

• 약수를 모두 찾은 후, 작은 순서로 정렬하여 K번째 작은 약수를 찾는다.

출력

• 약수의 개수가 K 보다 크거나 같다면, 정렬된 리스트에서 K 번째 약수를 출력한다.
• 약수의 개수가 K 보다 적다면 0을 출력한다.

✔️ 정렬 방법

sorted(divisor)

• 리스트 혹은 문자열 등을 내장함수로 이용해 정렬할 수 있다.
• sort(), sorted() 내장 함수가 있고, 디폴트 값은 오름차순이다.
• 내림차순으로 정렬하고자 할 때는 인자로 reverse = True 를 넘겨주면 된다.

Solution

N, K = map(int, input().split())
divisor = []  # 약수를 담을 리스트
for i in range(1, int(N**0.5) + 1):
    if N % i == 0:
        divisor.append(i)
        if N // i != i:
            divisor.append(N // i)

if len(divisor) >= K:
    print(sorted(divisor)[K - 1])
else:
    print(0)

 

📌 주의할 점

• 찾아야 할 K 번째보다 약수의 개수가 작으면 0으로 출력하는 조건 
• 약수 개수 기준으로 조건을 나눌 때 약수 개수와 K가 같은 것도 K번째 수를 뽑을 수 있다.
• 약수(몫과 나머지)가 같은 수일 경우 하나만 약수 리스트에 추가하기

---

👩‍💻 회고

위의 주의할 점들은 내가 미처 고려하지 못하고 풀어서 한번에 제출이 실패했던 이유를 모아놓은 것이다. 

---