[백준 2501번] N의 K번째 약수 출력하기 (시간복잡도 줄이기)

goal

자연수 n과 k를 입력 받아서 n의 k번째 약수를 출력하는 프로그램

참고자료

백준 2501번

수정, 개선이 필요할 경우 지적해주시면 감사하겠습니다.
참고할 수 있는 자료나 코드를 개선할 수 있는 부분을 알려주시면 감사하겠습니다.

---

1. 목표

• 자연수 n과 k를 입력 받아서 n의 k번째 약수를 출력하는 프로그램을 작성하세요.
  • 단, k가 n보다 크면 0을 출력합니다.

1-1 아이디어

1. N = A * B 이므로 N의 제곱근으로 시간복잡도를 줄인다
   • 약수는 list에 저장합니다.
2. 반복문을 통해 약수list에 a, b를 저장합니다.
   • 이때 반복문을 한 번 돌때마다 약수list에 a, b를 동시에 저장해줍니다.
3. 만약, A == B라면 중복되어 list에 저장되기 때문에 조건으로 이를 방지합니다.
4. 모든 처리를 한 후, list를 정렬하고 k가 n보다 큰 경우인지 확인합니다.
   만약 k가 n보다 크면 0을 출력하고 아니면 약수 list에서 k번째 수를 출력합니다.

def getDivisor (n: int, k:int) -> int :
    n_lists = [] # 약수를 저장할 list 생성
    n_measure = int(n ** (1/2)) + 1 # N의 제곱근을 저장하는 변수

    for i in range(1, n_measure) :
        # n이 i로 나눠지면 if문 실행
        if n % i == 0 :
            n_lists.append(i) # 직관적 이해 -> a, b에서의 a 저장
            if i * i == n : continue # # 직관적 이해 -> 만약 a * a 가 n이라면 반복문으로 점프
            n_lists.append(int(n//i)) # 직관적 이해 -> a, b에서의 b 저장

    n_lists.sort() # 저장된 약수 정렬
    result =  int(0) if len(n_lists) < k else n_lists[k-1] # 문제 조건이 부합하면 0 출력 아니면 k번째 약수 출력
    return result

def main() :
    n, k = map(int, input().split())
    print(getDivisor(n, k))

if __name__ == "__main__" :
    main()