소인수분해 - Java [프로그래머스 입문]

 

❤️ Problem

• 문제
  소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

 

• 제한 사항
  • 2 ≤ n ≤ 10,000

 

• 입출력 예 & 설명

no	n	result
1	12	[2, 3]
2	17	[17]
3	420	[2, 3, 5, 7]

1. 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.
2. 17은 소수입니다. 따라서 [17]을 return 해야 합니다.
3. 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

 

---

 

💛 Solution

풀이 1

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
class Solution {
    public int[] solution(int n) {

        Set<Integer> st = new TreeSet<Integer>();
        int primefactor = 2;
        while (primefactor<=n) {
            if(n%primefactor==0) {
                st.add(Integer.valueOf(primefactor));
                n /= primefactor;
            } else {
                primefactor++;
            }
        }

        int[] arr = new int[st.size()];
        Iterator iter = st.iterator();
        for(int i =0; i<st.size(); i++) {
            if(iter.hasNext()) {
                arr[i] = (int) iter.next();
            }
        }

        return arr;      
    }
}

 

처리속도에 대한 보완이 필요해 보인다

 

풀이 1에 대한 결과

 

---

 

풀이 2

import java.util.ArrayList;
import java.util.List;
class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>();
        int primeFactor = 2;
        while(n >  1){
            if(n%primeFactor==0){
                if(!list.contains(primeFactor))
                    list.add(primeFactor);
                n /= primeFactor;
                continue;
            }
            primeFactor++;
        }
        int[] answer = new int[list.size()];
        for(int i=0; i<answer.length; i++) {
            answer[i] = list.get(i);
//                System.out.println(answer[i]);
        }
    return answer;
    }
}

 

처리속도 보완 완료

 

풀이 2에 대한 결과

 

---

 

💜 Comment

풀이 1의 코드 처리 속도가 느렸던 이유는 데이터의 중복을 피하려 TreeSet을 사용했기 때문이다.

TreeSet을 사용하여 중복방지 + 순서유지 두 효과를 노려봤지만 나중에 TreeSet에서 Array로 값을 내보내는 과정에서 처리 속도가 현저하게 느려진 것으로 추정된다.

TreeSet의 특징에만 꽂힌 나머지 활용성을 생각하지 않았던 것 같다. Set에 값을 삽입할 때 정해진 순서가 없기 때문에 Array나 ArrayList처럼 인덱스로 값을 추출하는 방식이 통하지 않는다는 것을 몰랐다.

따라서 풀이 2에서는 Set을 사용하지 않았다. ArrayList를 사용하되 중복검사를 위해 ArrayList에 이미 값이 없는 경우에만 해당 값을 삽입하도록 하였다. 이후에는 ArrayList의 값을 Array로 전달하면 끝.

 

---

 

🤍 Concept

Set

• Collection 자료구조 중 하나인 인터페이스
  ( == Collection interface를 상속하는 자료 구조)
• 순서와 상관 없이 "값"의 존재유무를 확인하기 위한 용도로 주로 사용

 

Set의 특징

• 값 중복 불가능
• 값 삽입 시 순서를 보장하지 않음
• 정렬 불가능 (예외: TreeSet)
• 동기화 불가능 (not thread-safe)
• 원시형 값은 저장이 불가능
• 값 출력 시 반복문 또는 Iterator로 출력 (<-> ArrayList는 get 사용)Set의 종류

public static void main(String[] args) {
	HashSet<Integer> set = new HashSet<>();
	for (int i = 0; i < 10; i++) {
    	set.add(i);
    }
	//Iterator 사용하여 값 꺼내기
	Iterator<Integer> iter = set.iterator();
	while(iter.hasNext()){
    	System.out.println(iter.next());
	}
	//반복문으로 값 꺼내기
	for(int i : set) {
		System.out.println(i);
	}
}

 

1.  HashSet
   • HashMap과 Set 인터페이스를 상속
   • 가장 빠른 임의 접근 속도 (가장 성능이 좋음)
   • 정렬 불가능
   • 순서를 보장하지 않음
2. TreeSet
   • Tree와 Set 인터페이스를 상속
   • HashSet보다 처리 속도는 느림
   • 정렬 가능 (값 삽입과 동시에 정렬)
   • 정렬 방법을 지정할 수 있음
   • 최대값 및 최소값 메소드, 통계 메소드 존재
3. LinkedHashSet
   • 값 삽입 순서를 보장
   • 연결된 목록 형태로 구현됨 -> 느리다
   • 성능상의 이유로 잘 사용하지 않는다

 

 

참고한 블로그
https://bangu4.tistory.com/203 [Java] Set 인터페이스와 클래스 - 총정리
https://bangu4.tistory.com/194 [Java] Java Collection 구조 정리