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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

프로그래머스

---

2. 내가 푼 방법

종이조각을 모아 만들 수 있는 모든 값을 구하는 단계와, 그 후에 소수를 판별하는 단계를 가질 수 있다.

만들 수 있는 모든 값을 구하는 findAll 함수, 소수 판별하는 check 함수를 만들었다.

최종적으로 check 함수의 리턴 값이 true 일 경우에 answer++ 해주고 끝ㅎㅎ

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/Programmers/blob/main/Solution_%EC%86%8C%EC%88%98%EC%B0%BE%EA%B8%B0.java

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        
        Set<Integer> set = new HashSet<>();
        
        // 모든 경우의 수
        for (int i = 1; i <= numbers.length(); i++) {
            boolean[] check = new boolean[numbers.length()];
            
            findAll(set, numbers, new StringBuilder(), i, check);
        }
        
        // 소수인지 판별
        for (Integer s : set) {
            if (check(s)) answer++;
        }
        
        return answer;
    }
    
    public boolean check (int n) {
        if (n == 0 || n == 1) return false;
        
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public void findAll (Set<Integer> set, String numbers, StringBuilder sb, int total, boolean[] check) {
        if (sb.length() == total) {
            if (sb.length() == total) {
                set.add(Integer.parseInt(sb.toString()));
            }
            return;
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (check[i]) continue;
        
            check[i] = true;
            sb.append(numbers.charAt(i));
            
            findAll(set, numbers, sb, total, check);
            
            sb.deleteCharAt(sb.length()-1);
            check[i] = false;
        }
    }
}

---

4. 결과 및 회고

소수 판별 알고리즘도 몇 번 풀고 나니까 외워지긴 했는데 for문이 2부터 시작하는 것만 주의하면 될 것 같다.

계속 풀어보장!