[코딩 테스트 연습 입문] 소인수분해

문제

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

 

❗제한사항❗

• 2 ≤ n ≤ 10,000

 

입출력 예

 

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

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

 

✔풀이

def solution(n):
    answer = []
    
    for i in range(2,n+1):
        while n%i==0:
            answer.append(i)
            n=n//i
            
    set_answer=set(answer)
    answer=list(set_answer)

    return sorted(answer)

📝설명

for문과 while문을 사용해서 n의 소인수들을 중복하여 표시하도록 하고, 

for문이 끝나면 set로 변환해서 중복을 없애도록 한다.

중복을 없앤 후 list로 다시 변환하고, sorted()를 이용하여 정렬하였다.

➕개선한다면?

if n==1: break 사용으로 소요시간 단축

 

👑모범 답안

🔎while문과 if문의 조합이다.

d를 2로 먼저 정의하고, while문의 조건은 d가 n보다 작거나 같을 때로 둔다.만약 n를 d로 나눈 나머지가 0이라면, n은 n에서 d를 나눈 값으로 정의한다. 그리고, 이 d가 answer에 없다면 추가하도록 한다.만약 n을 d로 나눈 나머지가 0이 아니라면, 해당 수에서는 소인수분해가 불가능하다는 말이므로 d에 d+1의 값을 정의하여 while문을 실행하도록 한다.

 

👀느낀 점

: 정답으로 인정받은 첫 코드가 실은 시간을 무지하게 잡아먹었다.

for문을 n까지 돌리려고 하다보니 그랬는데, 개선할 점을 찾다보니 이미 소인수분해가 다 된 수의 for문을 굳이 n까지 돌릴 필요는없다는 생각이 들었다. 그래서 if문과 함께 break문을 넣었고, 소요시간도 줄어들었다.

코드을 짜는 것 뿐만 아니라 시간에 대한 생각도 하면서 더 나은 코드를  어떻게 만들 것인지에 대한 고민도 계속 해야겠다.