[알고리즘 문제풀이] 프로그래머스 소수 찾기

ㅠ.ㅠ 매일 매일 한 문제씩은 풀자고 2021 들어서 다짐해두고 일주일에 한 문제 꼴로 풀고있다니.. 더 열심히 살아보장구요..

먼저 문제의 링크는 아래와 같다 ! 코딩테스트 연습 고득점 kit에 완전 탐색 분류에 level2 문제다 !
https://programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다

풀이 방법

아주 아주 간단한 문제이기 때문에 간단하게 설명하도록 하겠다 ! 먼저 문제를 보고 당연스럽게 순열을 구해야겠다고 생각했다. 그 후에 구한 각 값들이 소수인지 판별하며 카운팅하면 된다. 그리고 설명한 그대로 코드로 구현해 나갔다.
순열을 구현할 때는 각 원소들을 그래프의 노드로 생각하고, 모든 노드가 연결되어 있다고 그래프를 상상한 후에 재귀를 통한 탐색을 구현하여 n개의 노드를 방문한 경우 하나의 결과값이 만들어진 것이다. 결과 값을 저장하는 과정에서 중복을 체크하는 것이 더 효율적이라고 판단하여 그렇게 구현하였다. 소수는 약간의 차이지만 시간을 줄이기 위해서 잘 알려진대로 제곱근까지만 반복하여 구하는 방식으로 구현하였다.

코드

import java.util.*;

public class Solution {
    public static ArrayList<Integer> allNumbers = new ArrayList<>();

    public static boolean isPrime(Integer num){
        if(num <= 1) return false;
        for(int i=2; i<=Math.sqrt(num); i++){ if(num%i == 0) return false; }
        return true;
    }

    public static void permutaion(int n, ArrayList<Integer> number, boolean[] visited, String value){
        if(value.length() == n){
            if(!allNumbers.contains(Integer.parseInt(value))){
                allNumbers.add(Integer.parseInt(value));
            }
            return;
        }
        for(int i=0; i<number.size(); i++){
            if(visited[i]) continue;
            value += number.get(i);
            visited[i] = true;
            permutaion(n, number, visited, value);
            value = value.substring(0, value.length()-1);
            visited[i] = false;
        }
    }

    public static int solution(String numbers) {
        ArrayList<Integer> number = new ArrayList<>();
        boolean[] visited = new boolean[numbers.length()];
        for(int i=0; i<numbers.length(); i++){
            number.add(Integer.parseInt(String.valueOf(numbers.charAt(i))));
            visited[i] = false;
        }
        for(int i=0; i< number.size(); i++){ permutaion(i+1, number, visited, ""); }
        int count = 0;
        for (Integer allNumber : allNumbers) { if (isPrime(allNumber)) count++; }
        return count;
    }
}