프로그래머스 : 소수 찾기 (Java)

🔗 문제 링크

코딩테스트 연습 - 소수 찾기

---

📖 풀이 과정

- 완전탐색 유형의 문제입니다.
- 풀이는 두가지로 나뉘어집니다. 
  - 첫째, 소수 판별
  - 둘째, 완전탐색을 통한 문자열 -> 숫자 만들기
- 소수 판별은 다른 문제와 유사하게 풀었으며 효율성 관련한 이슈가 없어서 패스하겠습니다!
- 문자열에서 완전탐색을 통해 새로운 숫자를 만들어야 합니다.
- 그러므로 저는 재귀를 이용하여 str이라는 변수에 문자열을 새로 만든 문자열을 담았습니다.
  - 마지막에 substring으로 문자를 수정하는 이유는 완전탐색이므로 str 변수를 원상태로 돌리기 위함입니다.
  - visited 변수를 되돌리는 것과 같은 이유입니다!
  - 새로 만드는 문자열(str 변수)의 길이가 for 반복문의 idx 변수와 같아지면 메소드를 종료합니다.
- 새로 만든 문자열(str 변수)를 Set 자료구조에 넣어 중복을 차단합니다.
- 최종적으로 Set을 돌며 소수 판별 후 개수를 구합니다.

---

💻 코드

import java.util.*;

class Solution {
    static Set<Integer> set = new HashSet<>();
    static boolean[] visited;
    
    public int solution(String numbers) {
        String str = "";
        int count = 0;
        visited = new boolean[10];
        for(int i = 0; i< numbers.length(); i++){
            createNumber(numbers,str,i+1);
        }
        
        Iterator<Integer> iter = set.iterator();
        while(iter.hasNext()){
            int value = iter.next();
            System.out.println(value);
            if(isPrime(value)){
                count += 1;
            }
        }
        return count;
    }
    
    private boolean isPrime(int number){
        if(number <= 1){
            return false;
        }
        for(int i = 2; i * i < number + 1; i++){
            if(number % i == 0){
                return false;
            }
        }
        return true;
    }
    
    private void createNumber(String numbers, String str, int limit){
        if(str.length() == limit){
            Integer number = Integer.parseInt(str);
            set.add(number);
            return;
        }
        
        for(int i = 0; i< numbers.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                str += numbers.charAt(i);
                createNumber(numbers,str,limit);
                visited[i] = false;
                str = str.substring(0,str.length()-1);
            }
        }
    }
}