[Java] 프로그래머스_42839 : 소수 찾기

완전탐색

소수 찾기 - Level2

 

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

 

재귀 정의

1. 상태

주어진 숫자들을 사용해서 숫자를 조합해 나가야 한다. 하나의 숫자를 계속해서 이어 붙여 나가야 하므로 상태에는 지금까지 만들어 놓은 숫자 comb, 사용할 수 있는 종이 조각들 numbers 로 2가지 변수가 포함된다.

 

2. 종료 조건

모든 경우를 확인해보아야 하므로 더 이상 숫자를 만들 수 없을 때(numbers가 비어있을 때) 재귀가 종료된다.

따라서 이 재귀의 종료 조건은 (comb, 0)이다.

numbers는 숫자들의 배열 혹은 집합으로, 0으로 표기해서 비어 있다는 것을 나타냈다. 이때는 만들 수 있는 숫자가 comb밖에 없다. 따라서 comb가 소수인지에 따라 종료 조건이 정의된다.

 

3. 점화식

만들어 놓은 숫자 comb에 사용할 수 있는 종이 조각 중 하나를 이어 붙여 상태를 전이시켜 나가야 한다.

또, comb 자체가 소수인 경우도 확인해야 한다.

=> (acc * 10 + n, numbers - n)

ㄴ + 연산을 기준으로 앞부분은 comb의 소수 여부에 따라 comb가 소수 집합에 포함될지 결정되고, 뒷부분은 numbers에 포함된 모든 정수에서 comb 뒤에 이어 붙이고, numbers 집합에서 해당 정수를 제외한 상태로 전이시킨다.

ㄴ 그리고 전이된 상태의 결과를 모두 더하면 원래 상태의 결과가 된다.

 

 

풀이1

import java.util.*;
import java.util.stream.*;

class Solution {
    
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    private Set<Integer> getPrimes(int comb, List<Integer> numbers) {
        // if (numbers.isEmpty()) {
        //     if (isPrime(comb)) return Set.of(comb);
        //     return Set.of();
        // }
        
        Set<Integer> primes = new HashSet<>();
        // 점화식 구현
        if (isPrime(comb)) primes.add(comb);
        
        // 종료 조건에서 comb의 소수 여부에 따라 집합을 생성하는 부분이 점화식에서 처음 집합을 생성하는 부분과 중복되는 것을 해결
        // if (numbers.isEmpty()) return primes; // 종료 조건에서 numbers 가 빈 리스트이므로 isEmpty()로 메서드를 종료하지 않아도 아래 for문에서 numbers에 포함된 원소가 없기 때문에 수행되지 않고 primes를 반환하므로 필요 없음
        
        // 상태 전이 구현
        for (int i = 0; i < numbers.size(); i++) {
            // numbers.get(i)로 상태 전이 진행
            int nextComb = comb * 10 + numbers.get(i);
            
            List<Integer> nextNumbers = new ArrayList<>(numbers);
            nextNumbers.remove(i);
            
            // 재귀를 이용하여 전이 상태에 대한 부분 문제를 풀고, 그 결과 집합을 현재 풀고 있는 상태의 결과 집합에 합침
            primes.addAll(getPrimes(nextComb, nextNumbers));
        }
            
        return primes;
    }
    
    public int solution(String nums) {
        List<Integer> numbers = nums.chars()
            .map(c -> c - '0')
            .boxed()
            .collect(Collectors.toList());
        
        return getPrimes(0, numbers).size();
    }
}

 

 

 

에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 알고리즘이다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

그림의 경우, 112 > 120

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

 

에라토스테네스의 체를 프로그래밍 언어로 구현

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		// 사용자로부터의 콘솔 입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}

 

=> 해당 알고리즘을 이용하여 아래와 같은 소수 판별 메서드를 만들었다.

 

private boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

 

 

ㄴ if (n <= 1) return false; : 먼저, 1보다 작거나 같은 숫자는 소수가 아니므로 false를 반환한다.

ㄴ for (int i = 2; i * i <= n; i++) : 2부터 시작해서 i * i가 n보다 작거나 같을 동안에 루프를 돈다. 더 큰 수로 나누어봤자 이미 작은 수로 나누어진 경우를 다시 확인하는 것이기 때문에 불필요한 계산을 줄이기 위함이다.

=> 여기서 i * i를 사용하는 이유

 i * i를 사용하는 이유는 소수 판별의 효율성을 높이기 위함이다.

만약 i * i를 사용하지 않고, i <= Math.sqrt(n)와 같이 사용한다면, 매번 제곱근을 계산해야 한다. 이는 계산 비용이 크기 때문에 성능에 영향을 미칠 수 있다.

i * i를 사용하면 한 번의 곱셈만으로 제곱을 계산할 수 있으며, 이는 제곱근을 계산하는 것보다 훨씬 효율적이다.

또한, i * i <= n 조건이 성립하는 동안에는 i <= Math.sqrt(n) 조건도 성립한다.

종합적으로, i * i를 사용함으로써 소수 판별 알고리즘의 성능을 향상시킬 수 있다.

 

ㄴ if (n % i == 0) return false; : 만약 n이 i로 나누어 떨어진다면 즉, 나머지가 0이면 n은 소수가 아니다.

    그렇기 때문에 false를 반환한다.

ㄴ return true; : 위의 조건들을 모두 통과하면 n은 소수이므로 true를 반환한다.

 

=> 이러한 방식으로 모든 조건을 확인하면서 주어진 수가 소수인지 아닌지를 판별하는 간단한 알고리즘이다.

 

 

Collection

자바 9에서는 작은 컬렉션 객체를 쉽게 만드는 방법을 제공한다.
이외에도 8에서 추가된 메서드도 살펴본다.

 

Set

팩토리

Set.of 로 간단한 Set을 만들 수 있다.

Set<String> getPrimes = Set.of("sample1", "sample2", "sample3");

• 중복된 요소를 제공해 생성하면 java.lang.IllegalArgumentException 예외가 발생한다.

 

풀이2 (리팩토링)

import java.util.*;
import java.util.stream.*;

class Solution {
    
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    private Set<Integer> getPrimes(int comb, List<Integer> numbers, Set<Integer> primes) {
        
        // 점화식 구현
        if (isPrime(comb)) primes.add(comb);
        
        // 상태 전이 구현
        for (int i = 0; i < numbers.size(); i++) {
            // numbers.get(i)로 상태 전이 진행
            int nextComb = comb * 10 + numbers.get(i);
            
            List<Integer> nextNumbers = new ArrayList<>(numbers);
            nextNumbers.remove(i);
            
            // 재귀를 이용하여 전이 상태에 대한 부분 문제를 풀고, 그 결과 집합을 현재 풀고 있는 상태의 결과 집합에 합침
            getPrimes(nextComb, nextNumbers, primes);
        }
            
        return primes;
    }
    
    public int solution(String nums) {
        Set<Integer> primes = new HashSet<>();
        List<Integer> numbers = nums.chars()
            .map(c -> c - '0')
            .boxed()
            .collect(Collectors.toList());
        
        getPrimes(0, numbers, primes);
        return primes.size();
    }
}

 

ㄴ Set을 반환으로 사용하는 것은 재귀 호출이 종료될 때마다 모든 원소를 순회하기 때문에 시간 복잡도가 기하급수적으로 증가한다.

ㄴ 이를 해결하기 위해 위와 같이 Set을 반환하지 않고 매개변수로 전달해서 불필요한 원소 순회를 방지한다.

 

 

 

풀이3 (리팩토링)

import java.util.*;

class Solution {
    
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    private void getPrimes(int comb, int[] numbers, boolean[] isUsed, 
                           Set<Integer> primes) {
        
        // 점화식 구현
        if (isPrime(comb)) primes.add(comb);
        
        // 상태 전이 구현
        for (int i = 0; i < numbers.length; i++) {
            if (isUsed[i]) continue;
            
            // numbers[i]로 상태 전이 진행
            int nextComb = comb * 10 + numbers[i];
            
            isUsed[i] = true;
            getPrimes(nextComb, numbers, isUsed, primes);
            isUsed[i] = false;
        }
    }
    
    public int solution(String nums) {
        Set<Integer> primes = new HashSet<>();
        int[] numbers = nums.chars().map(c -> c - '0').toArray(); // 수정
        getPrimes(0, numbers, new boolean[numbers.length], primes); // 수정
        return primes.size();
    }
}

 

ㄴ 풀이2에서는 사용할 수 있는 숫자들을 전달하려고 List를 복사하고 원소를 하나씩 제거하고 있다.

ㄴ List에 포함된 원소 개수를 N이라고 할 때, List의 복사는 전체 원소를 순회해야 하므로 O(N) 시간 복잡도가 소요된다.

ㄴ 또, 원소의 삭제는 하나의 원소를 삭제한 후 해당 원소 뒤에 있는 모든 원소를 한 칸씩 앞으로 당겨야 하기 때문에 O(N)이 소요된다.

 

=> 숫자 정보와 사용 여부 정보를 나누어 전달하여 해결할 수 있다.

 

List 로 전달하는 numbers를 모든 숫자가 저장된 int형 배열 numbers 와 각 숫자의 사용 여부를 나타내는 isUsed로 분리한다.

private void getPrimes(int comb, int[] numbers, boolean[] isUsed,
			Set<Integer> primes) {

 

ㄴ 모든 숫자를 사용하는 것이 아니라 배열 isUsed에 false로 체크된(사용하지 않은) 숫자들을 골라서 사용해야 한다.

=>

 

for (int i = 0; i < numbers.length; i++) {
    if (isUsed[i]) continue;

    int nextComb = comb * 10 + numbers[i];

    // 재귀 호출
    isUsed[i] = true; // 이번 재귀에서 사용한 숫자를 사용했다고 체크
    getPrimes(nextComb, numbers, isUsed, primes); // 재귀 호출 수행
    isUsed[i] = false; // 재귀 호출이 종료되었을 때는 더 이상 해당 숫자를 사용하지 않으므로 다시 isUsed에 false로 체크
}

 

 

 

 

개인적으로는 정말 어려운 문제였다.

효율적인 코드를 작성하기 위해 더 공부를 많이 해야겠다는 생각이 들었다.