[programmers] '소인수분해' 문제 해설 및 정답코드

 

 

 

문제 출처

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

프로그래머스

 

 

✅ 문제 설명

자연수 n을 소인수분해하여 오름차순으로 정렬된 소인수 리스트를 반환하는 문제입니다.

• 소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것을 의미합니다.
• 예를 들어 12를 소인수분해하면 2 * 2 * 3으로 나타낼 수 있으며, 이때의 **소인수는 {2, 3}**입니다.
• n이 주어졌을 때, 소인수만 포함된 리스트를 반환해야 합니다.

---

 

 

🔍 입출력 예시

 

번호 n 결과

1	12	[2, 3]
2	17	[17]
3	420	[2, 3, 5, 7]

---

 

 

🛠 소인수분해를 이해하기

 

1️⃣ 소인수분해란?

소인수분해는 한 숫자를 오직 소수들의 곱으로 표현하는 과정입니다. 즉, 어떤 수를 소수(1과 자기 자신만을 약수로 가지는 수)로만 나누어 떨어지게 하는 것입니다.

 

2️⃣ 소인수분해를 차근차근 따라해보기

번호 예제 소인수분해 과정 결과

1	12	12 ÷ 2 = 6, 6 ÷ 2 = 3, 3 ÷ 3 = 1	[2, 3]
2	17	17은 소수이므로 그대로 반환	[17]
3	420	420 ÷ 2 = 210, 210 ÷ 2 = 105, 105 ÷ 3 = 35, 35 ÷ 5 = 7, 7은 소수이므로 반환	[2, 3, 5, 7]

---

 

 

🔥 최적화된 해결 방법

 

3️⃣ 소인수를 구하는 방법

1. 가장 작은 소수인 2부터 시작하여 n을 나눕니다.
2. n이 2로 나누어지면 2를 리스트에 추가하고, n이 더 이상 2로 나누어지지 않을 때까지 계속 나눕니다.
3. 다음 숫자로 넘어가 같은 과정을 반복합니다.
4. n이 1이 될 때까지 반복하며, 모든 소인수를 찾습니다.

 

4️⃣ 코드 분석

def solution(n):
    factors = []  # 소인수를 저장하는 리스트
    divisor = 2   # 가장 작은 소수부터 시작
    
    while n > 1:
        if n % divisor == 0:  # divisor로 나누어떨어지는지 확인
            factors.append(divisor)  # 소인수 추가
            while n % divisor == 0:  # 같은 소인수가 여러 번 나올 경우 제거
                n //= divisor
        divisor += 1  # 다음 숫자로 이동
    
    return factors  # 소인수 리스트 반환

 

 

📌 코드 변수 설명

번호 변수 설명

1	factors	소인수를 저장하는 리스트. 중복을 방지하여 저장됨.
2	divisor	나누는 수. 2부터 시작하여 하나씩 증가함.
3	while n > 1	n이 1이 될 때까지 반복하며 소인수를 찾음.
4	if n % divisor == 0	n이 divisor로 나누어떨어지면 소인수로 추가함.
5	while n % divisor == 0	n이 같은 소수로 나누어질 때까지 반복하여 제거함.

---

 

 

📌 실행 예제 및 결과

번호 입력 값 소인수분해 과정 결과

1	12	2, 2, 3 → {2, 3}	[2, 3]
2	17	소수이므로 그대로	[17]
3	420	2, 2, 3, 5, 7 → {2, 3, 5, 7}	[2, 3, 5, 7]

---

 

 

🔑 핵심 정리

번호 개념 설명

1	소인수분해	어떤 수를 나누어 떨어지는 소수들의 곱으로 표현하는 것
2	중복 제거	같은 소수가 여러 번 등장해도 한 번만 추가
3	최적화 방법	while문을 사용하여 n이 나누어질 때까지 나눔
4	시간 복잡도	O(√n)으로 효율적 풀이