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

▪︎ 문제

---

프로그래머스 소수찾기

▪︎ 알고리즘 설계

---

• 에라토스테네스의 체
  • 71 → 2의 배수인가? 3의 배수인가? 4의 배수인가? ••• 70의 배수인가?
  • 한 숫자가 소수인지 아닌지 판단하고 싶다면, 그 숫자에 루트를 씌운 값까지만 확인하면 된다.

▪︎ 코드

---

import java.util.*;

class Solution {
    HashSet<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        
        // 1. 모든 조합의 숫자를 만든다.
        recursive("", numbers);
        
        // 2. 소수의 개수만 센다.
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()) { // 다음게 있니?
            int number = it.next(); // 해당 값 꺼내오기
            if(isPrime(number))
                answer++;
        }
        
        // 3. 소수의 개수를 반환한다.
        return answer;
    }
    
    public void recursive(String comb, String others) {
        // 1. 현재 조합을 set에 추가한다.
        if(!comb.equals(""))
            set.add(Integer.valueOf(comb));
        
        // 2. 남은 숫자 중 한개를 더 해 새로운 조합을 만든다.
        for(int i = 0; i < others.length(); i++) {
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i+1));
        }
    }
    
    public boolean isPrime(int num) {
        // 1. 0과 1은 소수가 아니다.
        if (num == 0 || num == 1) 
            return false;
        
        // 2. 에라토스테네스 체의 limit을 계산한다.
        int limit = (int)Math.sqrt(num);
        
        // 3. 에라토스테네스 체에 따라 limit까지만 배수 여부를 확인한다.
        for(int i = 2; i <= limit; i++) {
            if (num % i == 0)
                return false;
        }
        
        return true;
    }
}

▪︎ 시간복잡도

---

O(n * n! + n! * √M)

▪︎ 틀린 이유

---

• 조합 생성에 대한 감 부족
  • 단순히 재귀를 생각했지만, 실제로 모든 숫자 조합(순열)을 만들고 중복을 제거하는 로직을 떠올리지 못함.
  • others.substring(0, i) + others.substring(i+1)와 같은 방식으로 남은 숫자를 재귀적으로 줄여가며 새로운 조합을 만드는 아이디어가 필요했다.
    • 지금까지 만든 조합(comb)과 아직 사용하지 않은 숫자들(others)
    • 현재 위치의 문자 하나를 선택하고, 해당 문자를 제외한 나머지 문자열을 others로 넘긴다.
• 시간 복잡도에 대한 막연한 불안
  • n! 복잡도가 부담스러워 보였지만, 실제 입력 범위에서는 충분히 처리 가능했다.
  • 문제에서 요구하는 입력 제한을 기반으로 알고리즘의 실현 가능성을 판단해야 한다.
• 에라토스테네스의 체와 소수 판별의 혼동
  • 에라토스테네스의 체 전체를 구현할 필요는 없으며, 단일 숫자 소수 판별 시 √M까지만 나눠보면 된다.
• 재귀의 올바른 활용 부족
  • 재귀적으로 조합을 생성하고, 생성된 숫자를 HashSet에 넣어 중복 제거 후 소수 판별하는 로직이 핵심이었다.
    • 숫자 조합에 대한 중복을 제거!

▪︎ 느낀점 / 기억할 정보

---

• 문제를 쪼개서 생각하기
  • “모든 숫자 조합 생성” → “중복 제거” → “소수 판별” → “개수 세기”
  • 단계별로 나누면 복잡한 문제도 쉽게 풀린다.
• 재귀의 활용 패턴 익히기
  • 재귀를 사용할 때는 현재 값(comb)과 남은 값(others) 어떻게 변형할지 명확히 정의해야 한다.
  • 부분 문자열을 줄여가면서 새로운 조합을 만들어나가는 방식은 다양한 문제에서 유용하다.
• 소수 판별 최적화 기억하기 - 에라토스테네스의 체
  • 소수 판별 시 2부터 √n까지만 확인하면 된다.
• 중복 제거의 중요성
  • 순열 생성 시 중복된 숫자가 생기기 쉽다.
  • HashSet을 활용하여 중복 제거하는 패턴 기억하자.
• 입력 제한 확인 습관
  • 시간 복잡도가 커 보이더라도 입력 크기를 확인하고 적용 가능한 알고리즘인지 판단하는 습관을 들이자.