99클럽 코테 스터디 15일차 TIL /[프로그래머스] 소수찾기

💡문제

[level 2] 소수 찾기 - 42839

문제 링크

성능 요약

메모리: 84.5 MB, 시간: 23.86 ms

 

 

---

🤔접근법

문제 요약

• 1개 이상 7개 이하의 자연수들을 개수 상관없이 한번씩만 뽑아서 만들 수 있는 숫자가 소수인지 판별하는 문제

범위 체크 및 시간복잡도 예상

• 1 ≤ numbers의 길이 ≤ 7
• numbers를 이루고 있는 숫자 들은 0 ~ 9 자연수 이다.
• $O(N^2)$ 보다는 작아야한다.

풀이법

⭕ 접근 방법. 완탐

1. 숫자 문자열로부터 가능한 모든 순열 생성:
   • 각 자리 숫자를 사용하여 순열을 만들고, 각 순열조합이 소수인지 확인
   • 자리수의 중복을 방지하기 위해 방문 여부를 체크하는 배열을 사용
2. 소수 판별:
   • 각 생성된 숫자가 소수인지 확인. 소수 판별은 2부터 해당 숫자의 제곱근까지의 수로 나누어지는지 확인하는 방식으로 수행하여 시간복잡도를 줄인다.
   • 소수라면 이를 HashSet 저장하여 중복된 소수의 처리를 방지한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N! \sqrt{N})$

 

 

---

😎SUCCESS

고냥 단박에 성공

 

👩‍💻 코드

import java.util.*;

class Solution {

    // 소수를 저장하는 HashSet, 중복 소수를 자동으로 제거함
    static HashSet<Integer> prime = new HashSet<>(); 
    // 각 종이 조각의 방문 여부를 체크하는 배열
    static boolean visited[]; 
    // 입력된 종이 조각 숫자 문자열
    static String nums; 

    // 주어진 종이 조각 숫자 문자열에서 만들 수 있는 소수의 개수를 반환하는 메서드
    public int solution(String numbers) {
        nums = numbers; // 전역 변수 nums에 입력된 숫자 문자열 할당
        visited = new boolean[numbers.length()]; // 숫자 문자열 길이만큼 방문 여부 배열 초기화

        // 숫자를 조합하여 소수를 찾는 메서드 호출
        makeNumber(0 , ""); 

        // HashSet에 저장된 소수의 개수를 정답으로 반환
        int answer = prime.size(); 
        return answer; // 소수의 개수 반환
    }

    // 주어진 깊이에서 숫자를 조합하여 소수를 찾는 메서드
    private void makeNumber(int depth, String number) {
        // 현재 조합된 숫자가 소수인지 확인
        if(!number.isEmpty()) {
            isPrime(number);
        }

        // 재귀 호출 종료 조건: 현재 깊이가 숫자 문자열 길이 이상일 때
        if(depth >= nums.length()){ 
            return; // 메서드 종료
        }

        // 숫자 문자열의 각 자리수를 순회하며 숫자 조합 생성
        for (int i = 0; i < nums.length(); i++) {
            if(visited[i]) continue; // 이미 방문한 자리수는 건너뜀
            visited[i] = true; // 현재 자리수 방문 처리
            number = number + nums.charAt(i); // 현재 자리수의 숫자를 조합에 추가
            makeNumber(depth+1, number); // 다음 깊이로 재귀 호출
            number = number.substring(0, number.length()-1); // 마지막에 추가한 자리수의 숫자를 제거
            visited[i] = false; // 방문 처리 해제
        }
    }

    // 주어진 문자열이 소수인지 확인하고, 소수라면 HashSet에 추가하는 메서드
    private void isPrime(String number) {
        int n = Integer.parseInt(number); // 문자열을 정수로 변환
        if(n == 0 || n == 1){ // 0이나 1은 소수가 아님
            return; // 메서드 종료
        }

        // 2부터 n의 제곱근까지의 수로 나누어지는지 확인
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) { // 나누어 떨어지면 소수가 아님
                return; // 메서드 종료
            }
        }

        // 소수라면 HashSet에 추가
        prime.add(n); 
    }
}