[Java : 프로그래머스] 소수 찾기

📝 문제

https://programmers.co.kr/learn/courses/30/lessons/42839?language=java

🎯 풀이

소수 판별은 똑똑한 수학자들이 만들어놓은
만능 풀이법이 있기 때문에 구현이 간단하다.

• 1은 소수가 아니다.
• 2는 유일한 짝수 소수다.
• 모든 짝수는 소수가 아니다.
• 그 외의 홀수는 3,5,7,9, … , 제곱근 까지 나눠본다.

이것이 소수를 판별하는 쉽고 빠른 방법이다.

---

그렇다면 소수를 판별할 순열은 어떻게 구하나?
파이썬에서는 간편하게 permutation 함수를 이용할 수 있었지만,
자바는 직접 구현해야한다!!…

재귀함수를 이용해서 접근하면 어찌저찌 떠올릴 수 있다.

1. 빈 문자열을 준비한다.
2. main함수로부터 입력된 숫자 문자열에서 i번째 문자를 떼어 빈 문자열에 넣는다.
3. 숫자 문자열에서 i번째 문자를 제외시킨다.
4. 문자열 길이만큼 1~3 과정을 반복해서 재귀로 보낸다.
   • 빈 문자열이 더 이상 빈 문자열이 아니라면? 순열목록에 넣는다.

---

그렇다면 순열목록은 어떤 자료구조를 사용하는게 좋을까?
중복되는 숫자는 챙길 필요가 없으므로, Set 류의 자료구조가 좋겠다.
자바의 Set 자료구조는 대표적으로 HashSet, LinkedHashSet, TreeSet이 있다.

• HashSet
  • 가장 대표적인 Set
  • “순서? 그런건 모르겠고 중복만 처리 해줄게.”
• LinkedHashSet
  • “니가 삽입한 순서대로 저장해줄게.”
• TreeSet
  • “오름차순으로 정렬해줄게. 대신 좀 느릴거야.”

일단 LinkedHashSet은 적합하지 않을 것 같고…
HashSet과 TreeSet 중에 고민이 되는데, 어떤게 더 빠를까?
테스트도 직접 진행해봤다. 테스트 결과는 가장 마지막에!

---

import java.util.*;
class Solution {
public void permutation(String PreNumbers, String Numbers, TreeSet PrimeSet) {
    // PreNumbers 를 계속해서 순열 TreeSet에 저장.
    if(!PreNumbers.equals("")) PrimeSet.add(Integer.valueOf(PreNumbers));

    int n = Numbers.length();
    for (int i = 0; i < n; i++){
      // PreNumbers에 i번째 글자 붙이기.
      // Numbers 에 i번째 글자 제외시키기.
      // 재귀 반복.
      permutation(PreNumbers + Numbers.charAt(i),
                  Numbers.substring(0, i) + Numbers.substring(i+1, n),
                  PrimeSet);
    }
  }

  public boolean isPrime(int n) {
    // 2는 유일한 짝수소수.
    if (n == 2) return true;
    // 1과 짝수는 소수 아님.
    if (n == 1 || n % 2 == 0) return false;
    // 제곱근까지 홀수로 나눠보기.
    for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
      if (n % i == 0) return false;
    }
    // 다 통과하면 소수.
    return true;
  }

  public int solution(String numbers) {
    // 순열을 저장하고, 소수 검출에 사용할 TreeSet
    TreeSet PrimeSet = new TreeSet<>();
    // 순열 저장.
    permutation("", numbers, PrimeSet);

    int answer = 0;
    // TreeSet에 남은 숫자가 있을 때 까지 반복.
    while (PrimeSet.iterator().hasNext()) {
      int PrimeNumber = (int) PrimeSet.iterator().next();
      PrimeSet.remove(PrimeNumber);
      // 소수라면 정답 증가.
      if (isPrime(PrimeNumber)) 
        answer++;
    }

    return answer;
  }

}

잘 돌아간다!

📊 테스트 결과

# HashSet 결과
테스트 1 〉	통과 (15.09ms, 53.2MB)
테스트 2 〉	통과 (77.90ms, 53.4MB)
테스트 3 〉	통과 (13.82ms, 53.5MB)
테스트 4 〉	통과 (28.13ms, 53.9MB)
테스트 5 〉	통과 (48.46ms, 57.7MB)
테스트 6 〉	통과 (15.89ms, 52.4MB)
테스트 7 〉	통과 (15.22ms, 53.6MB)
테스트 8 〉	통과 (46.82ms, 56.4MB)
테스트 9 〉	통과 (17.97ms, 52.8MB)
테스트 10 〉	통과 (76.00ms, 53.4MB)
테스트 11 〉	통과 (28.88ms, 53.1MB)
테스트 12 〉	통과 (16.71ms, 54.8MB)
------------------------------
평균 33.41ms

# TreeSet 결과
테스트 1 〉	통과 (15.01ms, 52.4MB)
테스트 2 〉	통과 (38.21ms, 53.8MB)
테스트 3 〉	통과 (18.08ms, 53.7MB)
테스트 4 〉	통과 (29.88ms, 56.4MB)
테스트 5 〉	통과 (45.19ms, 56.3MB)
테스트 6 〉	통과 (15.06ms, 53.7MB)
테스트 7 〉	통과 (17.93ms, 52.6MB)
테스트 8 〉	통과 (50.39ms, 58.6MB)
테스트 9 〉	통과 (30.17ms, 53.9MB)
테스트 10 〉	통과 (40.16ms, 54.2MB)
테스트 11 〉	통과 (24.29ms, 54.3MB)
테스트 12 〉	통과 (18.05ms, 53.8MB)
------------------------------
평균 28.54ms

TreeSet의 강점인 이진트리구조 탐색을 활용할 일이 없는 코드라
당연히 HashSet의 동작이 더 빠를 줄 알았는데,
의외로 결과로 TreeSet이 더 빠른 모습을 보여줬다!

아마 iterator.next 메소드를 사용하는 과정에서
탐색이 이루어지기 때문에 5ms의 속도차이가 발생한게 아닌가 싶다.