[Java] 소인수분해 - Programmers Q120852

프로그래머스(Programmers)를 통해 코딩 테스트 사전 연습한 사항입니다.

---

요약

• 출처: 프로그래머스(Programmers)
• 번호: 120852

 

코드

public class Java_120852 {
    public int[] solution(int n) {
        List<Integer> lst = new ArrayList<>();
        
        int share = 2;
        while(n > 1) {
            if(n % share == 0) {
                n /= share;
                lst.add(share);
            }
            else {
                share++;
            }
        }

        int[] answer = lst.stream().distinct().mapToInt(i -> i).toArray();
        return answer;
    }
}

 

풀이

소인수 분해 문제이면서 동시에 중복된 인수는 제거하여 추출하는 것이 핵심입니다. 

따라서 이 두 과정을 분리하여 생각하는 것이 시간 제한에 걸리는 요소를 줄이는 방법입니다.

 

소인수 분해 결과 값을 얻고 싶은 타켓 정수를 2부터 증가시켜 나누어 소인수를 획득합니다.

나누어 떨어지지 않는 경우 나누는 값을 증가시킵니다. 

이 때, 이미 획득한 소인수의 경우 리스트에 넣지 않아도 좋지만 검증 로직이 매번 수행되는 것이라 시간 제한에 걸릴 수 있습니다.

따라서 위에서 언급한 사항을 적용하여 소인수들을 구하는 로직과 중복을 제거하는 로직을 분리하였습니다.

만약 List의 중복 제거 API를 이용하지 않는 조건이 달린 경우에는 소인수를 구하는 로직과 중복되는 로직이 분리되지 않고 한 로직에서 검증하며 추가하는 방식으로 구현되어야 합니다.  

 

출처

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

 

저장소

https://github.com/Ardium/TIL/blob/master/CodingTest/Java/src/programmers/level0/Java_120852.java

 

 

---