[프로그래머스 | 파이썬 / 자바스크립트] 소인수분해(코딩테스트 입문/ level 0)

문제

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

프로그래머스

 

 

🐍파이썬

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

1️⃣ 2 ~ n까지 while문을 돌며 n이 i로 나누어지는 경우 n을 i로 나눈 몫으로 업데이트하고 i를 answer 배열에 저장

2️⃣ n이 더 이상 i로 나누어지는 경우 다음 i를 탐색

3️⃣ 중복 제거

 

🛑 주의

문제에는 <오름차순 정렬>이라는 요구조건이 존재한다.

set()은 원소의 순서를 무시하는 특성이 있기 때문에 set()에 들어간 원소를 리스트로 바꾸어 출력하기 전에 오름차순 정렬이 필요하다.

아래는 set()을 이용한 코드

def solution(n):
    answer = set()
    i = 2
    while i <= n:
        if n % i == 0:
            n //= i
            answer.add(i)
        else:
            i += 1
    return sorted(list(anwer))

두 코드의 시간 / 공간 복잡도

list 2개 사용 시

set 사용 시

 

 

다른 풀이 방법

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

while문 안에서 중복 체크까지 한번에 진행

 

 

 

🐥자바스크립트

function solution(n) {
    var answer = [];
    let i = 2;
    while(i <= n){
        if(n % i == 0){
            n /= i
            if(!answer.includes(i)){
                answer.push(i);
            }            
        } else {
            i++;
        }
    }
    return answer;
}

위 파이썬 <다른 풀이 방법>의 풀이처럼 while문 안에서 중복 체크까지 한번에 진행했다.

 

 

다른 풀이 방법

function solution(n) {
    var answer = [];
    for(let i = 2; i <= n; i++) {
        while (n % i === 0) {
            n = n / i;
            answer.push(i);
        }
    }
    return [...new Set(answer)];
}