[프로그래머스][PYTHON] Lv. 0 소인수분해

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/120852

 

어떻게 풀어야할지 감이 안잡혀 다른 사람의 풀이를 보았습니다ㅠㅠ

다른 사람 풀이

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

 

주어진 수를 소인수분해 하는 문제인데, 12 = 2 * 2 * 3일 때, answer에는 [2, 3]만 포함되어야 한다. 

소인수분해는 1부터가 아닌 2부터 시작하므로 x=2로 초기화해주고, 

x가 n보다 작을 경우에는 while문을 통해 반복을 하여 소인수를 찾는다. 

 

n % x == 0을 통해 소인수인지 판단하고, 만약 x가 n의 소인수이면 x가 answer에 존재하는지 판별 후, 

answer에 없으면 추가하고, n을 x로 나눈 몫으로 n 값을 바꾼다. 

예를 들어, 12의 소인수를 구한다고 했을 때, 

첫 소인수 x는 2이다. 따라서 n을 2로 나눈 몫인 6으로 n을 바꿔준다. 

 

더 이상 n이 x로 나누어 떨어지지 않으면 x+1을 통해 다음 소인수를 찾는 과정을 반복한다 ! 

즉, x를 2부터 하나씩 증가하며 그 수가 소인수인지 아닌지 체크하게 된다! 

 

ex. n = 60일 때, 
60 % 2 == 0 --> answer에 2 append / n을 30으로 변경
30 % 2 == 0 --> answer에 이미 2가 있으므로 append X
n = 15가 되었지만, x = 2로 나누어떨어지지 않으므로, x+1 --> 즉, x=3이 됨. 

15 % 3 == 0 --> answer에 3 append / n을 5로 변경
5 % 3 != 0 --> x = 3, 4 모두 나누어떨어지지 않음 --> x = 5가 됨
5 % 5 == 0 --> answer에 5 append  / n을 1로 변경 / x <= n을 만족하지 않으므로 while문 탈출

 

느낀점

직접 계산하라고 하면  쉽게 할 수 있을텐데 코드로 짜라고하니 너무 어려웠다ㅜㅜ

좀 어려웠던 문제이니 다음에 다시 한 번 풀어봐야겠다.