[코딩테스트] 완전탐색 - 소수 찾기

• 프로그래머스 완전탐색 - 소수 찾기

문제

---

입출력 예시

---

접근 방법

---

순열 (Permutation)

순열이란 모든 순서대로 뽑는 경우를 의미한다.

• 중복된 값이 저장되지 않도록 HashSet을 이용한다.
• String을 쪼개어 모든 조합을 만든다.
• 리스트를 순회하면서 소수의 갯수를 센다.

import java.util.*;
import java.lang.Math;

class Solution {
	HashSet<Integer> set = new HashSet<>(); // 중복 방지
    
    public boolean isPrime(int n) {
        if(n == 1 || n == 0) {
            return false;
        }
        
        for (int i = 2; i < n; i++) {
            if(n % i == 0) {
                return false;
            } 
        }
        return true;
    }
    
    public void recursive(String preStr, String str) { 
        //System.out.printf("recursive 시작: " + "preStr: "+ preStr + " str: " + str + "\n");
        if (!preStr.equals("")) {
            set.add(Integer.parseInt(preStr));
        }
        
        for (int i=0; i<str.length(); i++) {
            //System.out.printf("for문: " + i + " " + preStr + str.charAt(i) + " " + str.substring(0,i) + str.substring(i+1) + "\n");
            recursive(preStr + str.charAt(i), str.substring(0,i) + str.substring(i+1)); // 재귀
            //System.out.println("set: " + set);
        }
    }

public int solution(String numbers) {
        int answer = 0;
        
        recursive("", numbers);
        Iterator<Integer> I = set.iterator(); // 리스트 순회
        
        while(I.hasNext()) {  // Iterator의 메서드
            int num = I.next();
            if(isPrime(num)) 
                answer++;
        }
        return answer;
    }

디버깅

---

recursive 시작:  preStr:  str: 17
for문: 0 1 7
recursive 시작:  preStr: 1 str: 7
for문: 0 17 
recursive 시작:  preStr: 17 str: 
set: [1, 17]
set: [1, 17]
for문: 1 7 1
recursive 시작:  preStr: 7 str: 1
for문: 0 71 
recursive 시작:  preStr: 71 str: 
set: [1, 17, 7, 71]
set: [1, 17, 7, 71]

추가 수정

---

소수 구하기 - 에라토스테네스의 체

	public boolean isPrime(int n) {
        if(n == 1 || n == 0) {
            return false;
        }
        
        for (int i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }

i의 제곱이 n보다 작을 때까지 구한다.