프로그래머스 - 소수 찾기(Level 2)

1. 소수 판별

: 자연수 X가 소수인지 확인하기 위해서는

가운데 약수까지만 나누어 떨어지는지 확인하면 됨.

즉, 제곱근까지만 확인하면 된다. 

약수는 대칭적인 형태를 보이기 때문이다.

private boolean isPrime(int n) { //소수인지 아닌지 판별
    if (n <= 1) return false; //0,1은 소수아님
    for (int i = 2; i * i <= n; i++) { //2부터  
        if (n % i == 0) return false;
    }
    return true;
}

 

 

2. String.chars()

: String 문자들을 stream으로 만들어준다.

 

 

3.

 int[] numbers = nums.chars() //Stream으로 변환
                .map(c -> c - '0') //int로 변환
                .toArray(); //int 배열로 변환

 

 

 

4. 순열 구현

DFS 백트래킹으로 isUsed 배열을 이용하여  순열 구하기

isUsed배열 - 처리한 위치 값은 true로 설정

depth=1일 때 해당 할 수 있는 값이 [1,2,3] 정해지고

depth=2일 때는 depth가 1일 때 정한 숫자를 제외한 나머지 숫자가 나올 수 있고

depth=3일 때는 depth가 1,2일 때 정한 숫자를 제외한 나머지 숫자가 올 수 있다.

예를 들면 depth=1일 때 값을 1로 정했다면 depth=2일 때 1을 제외한 [2,3]에 있는 값 2 그리고 [2,3]에 있는 값 3 이 올 수 있고 depth=3일 때 1,2를 제외한 [3]에 있는 3 그리고 1,3을 제외한 [2]에 있는 2 값이 올 수 있게 되어 1이 맨 앞에 있는 때 표현할 수 있는 방법은 총 2가지이고 총숫자가 3개이기 때문에 2*3을 하면 6가지가 된다.

private void getPrimes(int acc, int[] numbers, boolean[] isUsed,
                       Set<Integer> primes) { //DFS 방법으로 순열 구현
    if (isPrime(acc)) primes.add(acc); //현재 누적된 숫자 acc가 소수라면 set에 담기

    for (int i = 0; i < numbers.length; i++) { //사용할 수 있는 모든 숫자에 대해 반복
        if (isUsed[i]) continue; //사용한 숫자라면 건너뛰기

        int nextAcc = acc * 10 + numbers[i]; //다음 순서의 숫자 생성(기존에 누적된 숫자에 10을 곱하고 현재 선택한 숫자 더하기)

        isUsed[i] = true; //사용한 숫자라고 true 표시
        getPrimes(nextAcc, numbers, isUsed, primes); //다음 depth로
        isUsed[i] = false; //마지막 depth까지 들어가면 이제 false로 
    }
}

 

 

 

전체 코드

 

import java.util.HashSet;
import java.util.Set;

public class 소수_찾기 {
    private boolean isPrime(int n) { //소수인지 아닌지 판별
        if (n <= 1) return false; //0,1은 소수아님
        for (int i = 2; i * i <= n; i++) { //2부터 제곱수까지
            if (n % i == 0) return false; //나누어떨어지면 false
        }
        return true;
    }

    private void getPrimes(int acc, int[] numbers, boolean[] isUsed,
                           Set<Integer> primes) { //DFS 방법으로 순열 구현
        if (isPrime(acc)) primes.add(acc); //현재 누적된 숫자 acc가 소수라면 set에 담기

        for (int i = 0; i < numbers.length; i++) { //사용할 수 있는 모든 숫자에 대해 반복
            if (isUsed[i]) continue; //사용한 숫자라면 건너뛰기

            int nextAcc = acc * 10 + numbers[i]; //다음 순서의 숫자 생성(기존에 누적된 숫자에 10을 곱하고 현재 선택한 숫자 더하기)

            isUsed[i] = true; //사용한 숫자라고 true 표시
            getPrimes(nextAcc, numbers, isUsed, primes); //다음 depth로
            isUsed[i] = false; //마지막 depth까지 들어가면 이제 false로
        }
    }

    public int solution(String nums) {
        Set<Integer> primes = new HashSet<>(); //중복되는 소수는 한번만 담기 위해 set 생성
        int[] numbers = nums.chars() //Stream으로 변환
                .map(c -> c - '0') //int로 변환
                .toArray(); //int 배열로 변환
        getPrimes(0, numbers, new boolean[numbers.length], primes); //0을 넣은이유: 1의자리부터 만들기 위해
        return primes.size(); //소수의 개수 반환
    }
}

 

여러 조합을 만들고 싶을 때는 dfs가 효과적이다.

---

다음 날 나의 풀이

: StringBuilder를 사용하여 시간이 위의 코드보다 시간이 더 소요됨.

import java.util.*;

public class Solution {
    
    public void count(int number,Set <Integer> set){ //소수인지 판별
        if(number<2)
            return;

        for(int i=2;i*i<=number;i++){
            if(number%i==0)
                return;
        }
        set.add(number);
    }

    public  void dfs(int num, String[] str, Set<Integer> set
            , StringBuilder sb, Boolean[] visited){
        if(num==str.length){
            return;
        }

        for(int i=0;i< str.length;i++){
            if(visited[i])
                continue;
            sb.append(str[i]);
            visited[i]=true;
            count(Integer.parseInt(sb.toString()),set);
            dfs(num+1,str,set,sb,visited);
            visited[i]=false;
            sb.delete(sb.length()-1,sb.length()); //마지막 글자를 제거하는 메소드
        }
    }

    public  int solution(String nums) {
       String[] str=nums.split("");

        Boolean[] visited=new Boolean[str.length];
        Arrays.fill(visited, false); //배열을 모두 false로 초기화
        Set<Integer> set=new HashSet<>();
        StringBuilder sb=new StringBuilder();
        dfs(0,str,set,sb,visited);
        return set.size();
    }

}

 

 

1. StringBuilder.delete( int start, int end)

: start부터 end-1의 위치의 글자를 제거하는 메서드

sb.delete(sb.length()-1,sb.length());

다음과 같이 작성하여 마지막 글자를 제거함.

 

 

2. Arrays.fill(배열 변수, 초기화할 값)

: 초기화하고 싶은 배열을 해당 값으로 초기화하는 메서드

Arrays.fill(visited, false);

다음과 같이 작성하여 visited 배열을 모두 false로 초기화