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

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

프로그래머스

 

---

 

- 문제 풀이

 

1.  숫자 조합 만드는 재귀함수 작성

    public int solution(String numbers) {

        // 아래 ""부분에 숫자 조합 만듬
        recursive("", numbers);

    }

 

// 중복을 제거하며 숫자 저장
HashSet<Integer> numbersSet = new HashSet<>();

public void recursive(String comb, String others) {
        // comb가 비어있지 않으면 현재 조합된 숫자를 numbersSet에 추가
        // 예시: comb = "12"일 때 numbersSet에 12 추가
        if (!comb.equals("")) {
            numbersSet.add(Integer.valueOf(comb));
        }
        
        
        // others 문자열에서 하나씩 문자를 선택해서 comb에 추가하고
        // 남은 문자들로 새로운 조합을 재귀적으로 생성
        // 예시: others = "123"일 때
        // 첫 번째 반복: i = 0, comb = "1", others = "23"
        // 두 번째 재귀 호출: recursive("1", "23")
        for (int i = 0; i < others.length(); i++) {
            // comb에 others의 i번째 문자를 추가
            // others의 i번째 문자를 제외한 나머지 문자로 재귀 호출
            recursive(
                    comb + others.charAt(i), // comb에 others의 i번째 문자를 추가
                    // i번째 문자를 제외한 나머지 문자열로 재귀 호출
                    // 예시: others = "123", i = 1일 때 others.substring(0, 1) + others.substring(2) => "13"
                    others.substring(0, i) + others.substring(i + 1)
            );
        }
        
        
    }

 

동작 과정

1. recursive("", "123")에서 시작합니다.
   • 현재 comb는 빈 문자열이고, others는 "123"입니다.
   • comb가 빈 문자열이므로, 아무것도 numbersSet에 추가되지 않고, others의 각 문자를 하나씩 처리하는 반복문이 시작됩니다.

첫 번째 반복 (i=0, others의 첫 번째 문자 "1"을 추가)

recursive("1", "23") 호출:

• 현재 comb = "1", others = "23".
• "1"은 비어있지 않으므로 numbersSet에 1을 추가합니다.
• 이후, others = "23"에서 다시 반복문을 돌며 숫자를 추가합니다.

두 번째 반복 (i=0, others의 첫 번째 문자 "2"을 추가):

recursive("12", "3") 호출:

• 현재 comb = "12", others = "3".
• "12"는 비어있지 않으므로 numbersSet에 12를 추가합니다.
• 이제 others = "3"에서 "3"을 추가합니다.

세 번째 반복 (i=0, others의 첫 번째 문자 "3"을 추가):

recursive("123", "") 호출:

• 현재 comb = "123", others = "".
• "123"은 비어있지 않으므로 numbersSet에 123을 추가합니다.
• 이제 others가 비어 있으므로 더 이상 재귀 호출을 하지 않고 종료합니다.

 

 

2. 소수 판별 함수 정의

// num = 29라면
    // lim = (int)Math.sqrt(29)는 약 5
    // i = 2: 29 % 2 ≠ 0
    // i = 3: 29 % 3 ≠ 0
    // i = 4: 29 % 4 ≠ 0
    // i = 5: 29 % 5 ≠ 0
    // 2부터 5까지의 숫자로 나누어 떨어지지 않았으므로, 29는 소수
    public boolean isPrime(int num) {
        // 1) 0과 1은 소수가 아님
        if (num == 0 || num == 1) return false;

        // 2) 제곱근까지만 확인하여 소수 여부 판단
        // Math.sqrt(16) = 4
        int lim = (int)Math.sqrt(num);
        for (int i = 2; i <= lim; i++) {
            // 나누어 떨어지면 소수가 아님
            if (num % i == 0) return false;
        }

        return true; // 소수임
    }

 

 

3. 최종 소수 개수 반환

 // 최종 소수 개수 반환
    public int solution(String numbers) {

        // 아래 ""부분에 숫자 조합 만듬
        recursive("", numbers);

        // 소수 개수셈
        int count = 0;
        for (int number : numbersSet) {
            if (isPrime(number)) {
                count++;
            }
        }

        return count;

    }

 

---

 

 

- 정답 코드

import java.util.*;
    
class Solution {
    
    // 숫자 조합이 들어올 hashSet(중복 제거)
    HashSet<Integer> numberSet = new HashSet<>();
    
    public void recursive(String comb, String others) {
        if(!comb.isEmpty()) {
            numberSet.add(Integer.valueOf(comb));
        }
        
        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) {
        if(num == 1 || num == 0) return false;
        
        int lim = (int)Math.sqrt(num);
        for(int i = 2; i <= lim; i++) {
            if(num % i == 0) return false;
        }
        return true;
    }
    
    
    public int solution(String numbers) {
        // 1. 숫자 조합 만들기 => 재귀함수 사용
        recursive("", numbers);
        
        // 2. 소수 판별하기
        int count = 0;
        for(int number : numberSet) {
            if(isPrime(number)) {
                count++;
            }
        }
        return count;
    }
}