[프로그래머스] 소인수분해 (Python)

문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 2 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

제한사항

• 2 ≤ n ≤ 10,000

입출력 예

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

입출력 예 설명

• 입출력 예 #1
  12를 소인수분해하면 2 2 3 입니다. 따라서 [2, 3]을 return합니다.

• 입출력 예 #2
  17은 소수입니다. 따라서 [17]을 return 해야 합니다.

• 입출력 예 #3
  420을 소인수분해하면 2 2 3 5 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

---

내가 푼 답 (틀림)

• 먼저 소수를 찾아내어 소수인 경우, n을 그대로 return 하고
• 그 외의 경우에서는 [2,3,5,7]리스트에서 for문을 돌면서 계속 나눠주는 방법으로 구상했다.
• 위의 입출력 예시는 맞았지만 제출했을 때 정답률 45%로 통과하지 못했다.

정답 풀이1

def solution(n):
    answer = []
    d = 2
    while d <= n:
        if n % d == 0:
            n /= d
            if d not in answer:
                answer.append(d)
        else:
            d += 1
    return answer

정답 풀이2

def solution(n):
    k = 2
    answer = []
    while n>1:
        if n%k==0:
            answer.append(k)
            while n%k==0:
                n//=k
        k+=1

    return answer