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

문제 원본 링크: programmers.co.kr/learn/courses/30/lessons/42839

카테고리: 완전탐색

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져 있다. 흩어진 조이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 한다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers 가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성하라. 

 

제한 사항

• numbers는 길이1 이상 7 이하인 문자열이다.

• numbers는 0~9 까지 숫자만으로 이루어져 있다.

• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져 있다는 의미이다.

입출력 예

String numbers = "17"; // return = 3
String numbers = "011"; // return = 2

 

풀이 과정

이번 문제는 나에게는 아직 많이 어려웠다. 순열 알고리즘을 알고 있어야 풀 수 있었고, 또한 숫자가 소수인지 판별하는 방법도 알아야 했는데, 둘 다 바로 떠오를 만큼 준비되어있지 않아 풀지 못했다. 순열 알고리즘과 소수 판별 함수 모두 다른 곳을 참고하였다. 아직 갈 길이 멀다. 

 

• 우선 HashSet을 전역변수로 생성하여 중복하지 않는 소수를 저장하기 위해 사용했다.

• 순열 알고리즘을 사용하여 배열 안에 있는 모든 숫자를 조합한다.

• 조합한 숫자가 소수인지 확인한다.

• 소수이면 set에 저장한다. 

• set의 사이즈를 리턴한다.

자바 코드

package problems.brute_force;

import problems.Problem;
import java.util.HashSet;

public class FindingPrime extends Problem {
    HashSet<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        String[] numbs = numbers.split("");
        for (int i = 1; i <= numbers.length(); i++) {
            perm(numbs, 0, numbers.length(), i);
        }

        return set.size();
    }

    /**
     * <순열 알고리즘/>
     * 참고: https://gorakgarak.tistory.com/522
     *
     * arr: 데이터를 가지고 있으면서 순서를 교환하는 배열
     * depth: 현재 트리구조에서 어떤 깊이에서 교환작업을 하고있는지를 확인하는 변수
     * n: 총 배열안에 들어있는 숫자, 고정값
     * k: 선택할 숫자의 개수
     * */
    private void perm(String[] arr, int depth, int n, int k) {
        StringBuilder numb = new StringBuilder();
        if (depth == k) { // depth가 k에 도달하면 사이클이 한 번 끝.
            for (int i = 0; i < k; i++) {
                numb.append(arr[i]);
            }

            if (!set.contains(Integer.parseInt(numb.toString()))) {
                if (isPrimeNumber(Integer.parseInt(numb.toString()))) {
                    set.add(Integer.parseInt(numb.toString()));
                }
            }
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth);
        }
    }

    private void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 소수인지 확인하는 함수
    private boolean isPrimeNumber(int n) {
        if (n <= 1) return false;
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

 

채점 결과

 

참고

- 깃허브 소스 코드: 링크