[프로그래머스/Level2] 소수 찾기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 접근

핵심

• 순열로 모든 숫자 조합을 찾는 것
• 숫자 중복 체크
• 소수 판별

dfs 알고리즘을 이용해 모든 숫자의 조합을 찾아가면서 중복되지 않는 숫자에 한해 소수 판별을 진행했다.

dfs를 이용하는 방법말고도 모든 숫자의 조합을 찾는 방법을 다른 풀이를 보면서 공부했다.

소스 코드

import java.util.HashMap;

class Solution {
    HashMap<Integer, Boolean> duplicate;
    int count;
    
    public int solution(String numbers) {
        duplicate = new HashMap<>();
        count = 0;
        
        for (int i = 0; i < numbers.length(); i++) {
            boolean[] visit = new boolean[numbers.length()];
            String curNumber = "";
            
            dfs(numbers, visit, i, curNumber);
        }
        
        return count;
    }
    
    public void dfs(String numbers, boolean[] visit, int idx, String curNumber) {
        curNumber += numbers.charAt(idx);
        Integer num = Integer.parseInt(curNumber);
        visit[idx] = true;
        
        //이미 체크한 숫자인지 판별
        if(!duplicate.containsKey(num)) {
            isPrimeNumber(num);
            duplicate.put(num, true);
        }
        
        for (int i = 0; i < visit.length; i++) {
            if (!visit[i]) {
                dfs(numbers, visit, i, curNumber);
                visit[i] = false; //다시 사용할 수 있게 풀어줌
            }
        }
    }
    
    //소수 판별
    public void isPrimeNumber(int num) {
        if (num <= 1) {
            return;
        }
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return;
            }
        }
        
        count++; //소수면 개수 증가
    }
}

참고 코드(순열)

public void permutation(String prefix, String numbers) {
  int length = numbers.length();

  if (!prefix.equals("")) {
      System.out.println(prefix);
  }

  for (int i = 0; i < numbers.length(); i++) {
  	  //자신을 제외한 문자열을 만들어 넘겨줌
      permutation(prefix + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i + 1, length));
  }
}