Menu

Subscribe

[JAVA/프로그래머스] 완전탐색_소수 찾기

HEESOO on Programmers

👀 문제

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

👊 첫 번째 도전

1. 설계

  1. String형 numbers를 쪼개서 int형으로 배열에 저장한다.
  2. 만들 수 있는 숫자를 모두 생성한다=>조합 이용.
  3. 소수 체크해서 갯수를 센다=>에라토스테네스의 체 이용.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

import java.util.HashSet;
import java.util.Set;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int solution(String numbers) {
        int answer = 0;
        String[] strArr=numbers.split("");
        int[] numArr=new int[strArr.length];
        for(int i=0;i<numArr.length;i++){
            numArr[i]=Integer.parseInt(strArr[i]);
        }
        Set<Integer> set=new HashSet<>();
        //1부터 만들 수 있는 최대 길이까지 숫자 조합
        for(int i=1;i<=numArr.length;i++){
            perm(strArr, 0, i, set);
        }
        answer=set.size();
        return answer;
    }
    public void perm(String[] arr, int depth, int k, Set set){//숫자 조합
        if(depth==k){//원하는 k개의 숫자가 세팅됐으므로 더이상 순열생성X
            print(arr, k, set);
            return;
        }
        else{
            for(int i=depth;i<arr.length;i++){
                swap(arr, i, depth);
                perm(arr, depth+1, k, set);
                swap(arr, i, depth);
            }
        }
    }
    public void swap(String[] arr, int i, int j){
        String temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public void print(String[] arr, int k, Set set){//숫자 연결
        StringBuilder s=new StringBuilder();
        for(int i=0;i<k;i++){
            //System.out.print(arr[i]);
            s.append(arr[i]);//숫자연결하기
        }
        //System.out.println();
        primeNumber(set, s);
    }
    public void primeNumber(Set set, StringBuilder s){//소수 체크
        int num=Integer.parseInt(String.valueOf(s));
        boolean prime=true;
        if(num<=1){
            return;
        }
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0){
                prime=false;
                break;
            }
        }
        if(prime){
            set.add(num);
        }
    }
}
  • public int solution(String numbers)
    • String[] strArr: numbers를 하나씩 쪼개서 배열에 저장한다.
    • int[] numArr: 쪼갠 strArr를 int형을 변환한다.
    • Set set: 생성한 숫자들은 중복될 수 있으므로 HashSet을 이용하여 중복을 제거한다.
  • public void perm(String[] arr, int depth, int k, Set set)
    • int depth: 현재 내 숫자 길이를 뜻한다.
    • int k: 만들 숫자 길이이다.

3. 코드 설명

  • public int solution(String numbers): numbers를 int형으로 변환하고, for문을 통해 1부터 종이 조각을 가지고 만들 수 있는 최대 길이만큼 숫자 조합 함수 perm()을 호출한다. for문이 끝나면 set에는 소수인 숫자들이 저장되어있으므로 set의 size를 리턴한다.
  • public void perm(String[] arr, int depth, int k, Set set): if 조건인 depth==k의 의미는, 현재 내 길이가 k와 같아졌으므로 원하는 k개의 숫자가 세팅되었다는 뜻이므로 더 이상 순열을 생성하지 않고 print()함수를 호출해 숫자를 연결해준다.
    else문은 아직 k만큼 길이 생성이 되지 않았을 경우이다. 이 경우에는 for문을 통해 현재 내 위치 depth부터 arr.length까지 돌면서 숫자 길이를 늘린다. 이때 숫자 조합을 위해 swap()을 호출하여 arr의 순서를 바꾼다(https://gorakgarak.tistory.com/522 참고). 배열이 변경되었다면 depth+1하여 다시 perm()함수를 호출한다(재귀). 이렇게 재귀를 계속 호출하다가 if문에 걸려서 return하면 그 다음 swap()으로 넘어간다. 다음 swap()을 진행할 수 있다는 것은 숫자 조합이 완성되었다는 뜻이다. 때문에 다시 swap()을 통해 배열을 다시 원상복구해준다. 다시 swap을 호출해주지 않는다면 이후 arr사용에 문제가 생긴다. 이후에 이상한 값이 나올 것이다.
  • public void swap(String[] arr, int i, int j): 배열 arr의 i와 j번째 값을 바꾼다.
  • public void print(String[] arr, int k, Set set): 숫자 조합이 완성되면 이 함수에 들어온다. 숫자들을 하나의 String으로 연결시켜주기 위함이다. 이를 위해 StringBuilder가 사용된다. StringBuilder의 append()메소드를 통해 String형을 연결(+)할 수 있다. 일반적으로 +=를 이용해 연결할 수도 있지만, 연결해야할 대상이 많은 경우에는 성능이 저하될 수 있다. 때문에 StringBuilder를 사용한다.
    for문으로 숫자가 하나로 연결되면 primeNumber()을 호출해 소수인지 확인한다.
  • public void primeNumber(Set set, StringBuilder s): 연결된 숫자 s를 int형으로 형변환하여 num에 저장한다. 숫자 1은 소수도, 합성수도 아니므로 HashSet에 저장하지 않는다. 2부터 num의 루트값까지 순회하며 나누어지는 값이 있는지 확인한다. 참고로 특정 숫자가 소수인지 판별할 때에는 처음부터 그 값까지 확인하지 않고 루트값까지만 확인해도 된다(에라토스테네스의 체). 나눠지는 값이 있다면 소수가 아니라는 의미이므로 for문을 종료한다. 나눠지는 값이 없다면 소수이므로 HashSet에 저장한다. 이때 만들어지는 숫자 num은 중복이 생길 수 있는데, HashSet에 저장함으로써 중복을 거른다.

4. 결과

실행결과 🤟 성공 🤟

👏 해결 완료!

소수를 체크하는 것은 어렵지 않았는데 숫자 조합을 생각하는 것이 어려웠다. 그래서 다른 사람 코드를 많이 참고했다. 어려운 문제였다.

참고