[프로그래머스] 소수 찾기 - 자바(Java)

문제 링크

프로그래머스

 

문제 설명

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

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

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

 

문제 풀이

이 문제는 numbers에서 추출한 한자리 숫자의 조합을 먼저 찾고, 조합한 수가 소수인지 판별하면 된다.

추출한 한자리 숫자의 조합은 dfs로 완전탐색을 이용해서 찾고, 찾은 수를 기준으로 소수 판별을 하면 된다.

 

이때 소수란, 1과 자기 자신 만을 약수로 가지는 수를 뜻한다.

어떤 수가 소수인지를 확인하기 위해서는 2부터 그 숫자 횟수만큼 반복하며 나누어떨어지는 수가 있는지 확인하는 방법도 있지만,

해당 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 더 빠르게 구할 수 있다.

 

* 제곱근까지만 반복해도 되는 이유

어떤 수 N이 1과 자신이 아닌 두 수의 곱으로 되어있다고 가정. 

(소수가 아닌 수) N = a * b 일때 n은 N의 제곱근이라고 표현하자. 

 

만약 a >= n이라면 a * b = N = n * n 이므로, b <= n 이 성립한다. 

따라서 N의 제곱근인 n까지만 검사를 하면 합성수를 이루는 a, b 중 작은 수(예시에서는 b)까지는 충분히 체크할 수 있고, 합성수가 존재하지 않으면 소수라고 할 수 있다. 

* 이때, 대량의 소수를 한번에 판별해야 하는 경우, 에라토스테네스의 체를 이용한다.

에라토스테네스의 체란 먼저 소수를 판별할 범위만큼 배열을 할당하여, 순서대로 수를 넣고, 이후 판별을 하면서 하나씩 지워나가는 방식이다.

1. 배열을 생성하여 초기화한다. 
   • boolean[] arr = new boolean[N] // N까지의 소수를 구하려 할때
2. 2부터 시작해서 배수에 해당하는 모든 수를 지운다. (=true로 값을 할당)
   • 지울때 자기 자신은 지우지 않고 저장해둔다. (소수이기 때문에)
     • i=2 : 2는 소수이므로 2는 true로 바꾸고, 4, 6, 8,... 등 N까지의 2의 배수는 false로 그대로 둔다.
     • i=3: 3은 소수이므로 true로 바꾸고, 4는 i=2일때 이미 소수가 아님이 판별되었기 때문에 넘어간다.
     • N까지 반복한다.
3. 소수로 판별된 수를 반환 
   • true로 설정된 값을 반환한다.

 

[풀이 과정]

이 문제에서는 특정 한자리 숫자들로 조합된 숫자들의 소수 판별을 해야하므로 

1. 숫자들로 조합할 수 있는 모든 경우의 수를 찾고
2. 찾은 수가 소수가 맞는지 판단

하면 된다.

 

[알고리즘, 구현방법]

먼저 숫자의 조합은 위에서 말한대로 완전탐색 중 DFS를 이용해서 찾는다.

dfs(numbers, "", 0);

public static void dfs(String numbers, String s, int depth) {
    if (depth > numbers.length()) return; // numbers 끝까지 순회하면 return

    for (int i=0; i<numbers.length(); i++) {
        if (!checked[i]) {
            checked[i] = true;
            set.add(Integer.parseInt(s + numbers.charAt(i)));
            dfs(numbers, s + numbers.charAt(i), depth+1);
            checked[i] = false; // 다음 조합을 위해 false로
        }
    }
}

 

방문하지 않은 문자를 기존 문자열(s)에 추가하는 방식으로 숫자를 추가했다.

숫자가 중복되면 안되므로 저장할 자료구조는 Set으로 정했다.

numbers 문자열의 특정 문자의 조합이 끝나면, 다음 조합을 위해 checked를 false로 돌려준다.

이 과정을 numbers 문자열을 문자 개수만큼(=문자열 길이) 반복하면 모든 조합을 찾을 수 있다.

 

그리고 조합한 수의 소수 판별은 해당 수의 제곱근까지 반복하여 나머지 연산 결과가 0이 아닌지 확인한다.

public static boolean isPrime(int num) {
    if (num < 2) return false;
    for (int i=2; i <= (int)Math.sqrt(num); i++) { // num의 제곱근까지 확인
        if (num % i == 0) return false;
    }
    return true;
}

 

 

코드

import java.util.*;
public class Solution {
	Set<Integer> set;
    boolean[] checked = new boolean[7]; // 조합한 수인지 (numbers는 최대 7자)
    
	public int solution(String numbers) {
   		set = new HashSet<>();
        // 문자열 numbers의 수 조합 찾기
        dfs(numbers, "", 0);

        int answer = 0;
        // 소수 판별
        for (int val: set) {
            if (isPrime(val)) answer++;
        }

        return answer;
    }

	public void dfs(String numbers, String s, int depth) {
        if (depth > numbers.length()) return; // numbers 끝까지 순회하면 return

        for (int i=0; i<numbers.length(); i++) {
            if (!checked[i]) {
                checked[i] = true;
                set.add(Integer.parseInt(s + numbers.charAt(i)));
                dfs(numbers, s + numbers.charAt(i), depth+1);
                checked[i] = false; // 다음 조합을 위해 false로
            }
        }
    }

    public boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i=2; i <= (int)Math.sqrt(num); i++) { // num의 제곱근까지 확인
            if (num % i == 0) return false;
        }
        return true;
    }
}