프로그래머스 - 소인수분해

프로그래머스 - 소인수분해

import java.util.LinkedHashSet;
import java.util.Set;

class Solution {
	public int[] solution(int n) {
		Set<Integer> set = new LinkedHashSet<>();
		for(int i=2; i<=n; i++) {
			if(n%i==0) {
				set.add(i);
				n = n/i;
			}
		}

		// 가장 마지막 n이 소수인지 검사
		int count =0;
		for(int k=2; k<=n; k++) {
			if(n%k==0)
				count++;
		}
		// 나눠 떨어지는 수가 1개 => 본인 뿐이니 소수, set에 넣는다.
		// 기존에 있는 값이라면 어차피 무시됨(Set)
		if(count==1)
			set.add(n);

		// 다시 카운트 0으로 초기화
		count = 0;

		// set에 소수가 아닌 약수가 들어있는지 검사
		// set은 순회하며 값을 제거하는 작업 동시에 할 시 Exception 발생할 수도 있어 별도의 Set 생성
		Set<Integer> nonPrimes = new LinkedHashSet<>();
		
		for(Integer a : set) {
			for(int j=2; j<=a; j++) {
				if(a%j==0) count++;
			}
			// 자기 자신 외에 나눠 떨어질 경우
			// 소수가 아닌 약수이므로 삭제
			if(count!=1) {
				nonPrimes.add(a);
			}
			// 다음 요소 검사를 위해 카운트 초기화
			count = 0;
		}
		
		// 소수가 아닌 Set 모두 삭제
		set.removeAll(nonPrimes);

		return set.stream()
			.mapToInt(Integer::intValue)
			.toArray();
	}
}

• 소인수분해
• 반복문으로 어떻게 할 수 있을지 고민하다가, 직접 하는 영상을 보니 i는 증가하고, 나누는 수는 감소하는것을 힌트로 얻었다.
• 이렇게 하면 가장 마지막에 남는 n이 i보다 작아지면 나누지 않으니 소수인지 검사를 해준다.
• 단 이렇게 하면, i가 소수가 아닐때도 나누어 떨어진다.
  • Set에 있는 요소 검사 필요
    ex) 252
    
  • Set 요소들을 순회 하면서 remove를 해주면 Exception 발생할 수도 있으므로, 별도 Set을 만들고 순회 다 한다음에 removeAll을 해준다.
  • LinkedHashSet의 경우 순서를 보장해주니 별도 sort를 하지 않음