[코드 풀이] 소수 구하기

문제 파악

주어진 숫자 중 서로 다른 3개를 골라 더했을 때, 나올 수 있는 소수의 개수를 구하라.

접근 방법

• 현재 코드에 적용된 방법

소수란 무엇인가?

• 1과 자기 자신 만을 약수로 갖는 수이다.
  

소수를 판단하는 방법

1. 단순히 2부터 n-1까지 나머지 연산자로 연산한다.
   - 이 과정에서 나머지가 0이 되는 수가 없다면 이 수는 소수인 것이다.
   → 하지만 이 방법은 2부터 n-1까지 반복 연산을 수행하므로 비효율적이다. 시간복잡도는 O(n-2)
   

• 소수의 특성
  

어떤 수 N은 작은 수 * 큰 수 형태로 이루어져 있다.

N의 제곱근 보다 큰 수로 N을 나눈다면 그 몫은 이미 이전에 걸러져 있다.

24 = 2 × 12  
24 = 3 × 8  
24 = 4 × 6  
24 = 6 × 4 ← 이 부분부터는 순서만 바뀐다.
24 = 8 × 3
24 = 12 × 2

24의 제곱근 = 약 4.89

4.89보다 큰 24의 약수는 6

하지만 6은 이미 4 * 6에서 걸러진다.

즉, 24의 제곱근 미만인 수만 확인하면 된다.

11이 소수인지 판별하려면?

11의 제곱근 = 약 3.31

3.31 미만인 수 1, 2

소수는 1과 자기 자신 만을 약수로 갖는 수이므로 1은 제외

2는 11의 약수인가? → ❌

그러므로 11은 소수이다.

Java에서 제곱근을 구하려면 Math.sqrt()를 사용하면 된다.

어떤 수 N이 소수인지 판별하려면?

for(int i = 2; i < Math.sqrt(N); i++) {
	if(N % i == 0) {
		break;
	}
}

이런 식으로 작성하면 된다.

• 서로 다른 숫자 3개를 뽑아야 한다.
  1. 배열의 시작 인덱스부터 3개의 숫자를 순차적으로 뽑는다.
     • arr[0], arr[1], arr[2]
       
       
  2. 그 후 arr[2]만 순차적으로 증가 시켜 더한다.
  3. arr[2]가 배열의 끝(arr[n])에 도달했다면, arr[1]과 arr[2]의 인덱스를 1 증가시킨다.
     • arr[0], arr[2], arr[3]
       
       
  4. 2 - 3의 과정을 반복한다.
  5. 최종적으로 아래와 같은 형태가 되면 arr[0]의 인덱스를 1 증가시킨다.
     • arr[0], arr[n-1], arr[n]
       → arr[1], arr[2], arr[3]
       
       
  6. 그 후 2 - 5의 과정을 반복하면 주어진 배열에서 3가지의 수를 더하는 모든 경우의 수를 얻을 수 있다.

위의 방법을 사용하여 코드를 작성해 본다.

→ 3중 for문을 사용하자.

for문의 시간 복잡도: O(n)

2중 for문의 시간 복잡도: O(n^2)

3중 for문의 시간 복잡도: O(n^3)

문제의 제한사항

배열의 길이 n은 3 ≤ n ≤ 50이다.

최악의 경우 50^3까지 반복할 수 있다.

50^3 < 10^8 이므로, 3중 for문을 사용해도 된다.

• 재귀 함수를 이용한 풀이

  class Solution {
      int answer = 0;
  
      public int solution(int[] nums) {
          comb(nums, 0, 0, 0); // 조합 뽑기 시작
  										         // 최초에는 아직 아무것도 뽑지 않았으므로 0, 0, 0
          return answer;
      }
  
  		// count = 뽑은 횟수
  		// sum = 뽑은 수의 합
  		// start = 다음에 뽑을 인덱스
      void comb(int[] nums, int count, int sum, int start) {
  		    // 3회 뽑았으면 소수 판별 시작
          if(count == 3) {
  		        // 합이 소수이면 개수 카운트
              if(isPrime(sum)) {
  	            answer++;
              }
              
              return;
          }
  				
  				// 반복문을 통한 재귀호출로 다음 숫자 뽑기
          for(int i = start; i < nums.length; i++) {
              comb(nums, count + 1, sum + nums[i], i + 1);
          }
      }
  
      boolean isPrime(int n) {
          if(n < 2) {
  	        return false;
  	       }
  	       
          for(int i = 2; i <= Math.sqrt(n); i++) {
              if(n % i == 0) return false;
          }
          
          return true;
      }
  }

• 에라토스테네스의 체를 사용한 풀이

  • 에라토스테네스의 체

    주어진 자연수 N이 소수이기 위한 필요 충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.

    어떠한 수1과 어떠한 수2를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 해당 수의 제곱근 이하이기 때문이다.

    → 즉, 2부터 시작해서, 그 수의 배수를 모두 지워나간다. 그러면 남아 있는 수는 모두 소수가 된다.

    예시: 1부터 30까지의 모든 소수 구하기

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

    1. 2는 소수니까 제외한 후 2의 배수를 모두 제거한다.

       2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X
       

    2. 3은 소수이므로 제외한 후 3의 모든 배수를 제거한다.

       2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X
       

    3. 5도 소수이므로 제외한 후 5의 모든 배수를 제거한다.

       2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X

       최종적으로 소수만 남게 되었다.

       코드로 구현해보자

       import java.util.Arrays;
       
       public class SieveExample {
           public static void main(String[] args) {
               int n = 30; // 1부터 30까지 소수 찾기
               boolean[] isPrime = new boolean[n + 1];
               Arrays.fill(isPrime, true); // 일단 전부 소수라고 가정
               isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님
       
               for (int i = 2; i * i <= n; i++) {
                   if (isPrime[i]) {
                       for (int j = i * i; j <= n; j += i) {
                           isPrime[j] = false; // i의 배수 제거
                       }
                   }
               }
       
               System.out.println("소수 목록:");
               for (int i = 2; i <= n; i++) {
                   if (isPrime[i]) {
                       System.out.print(i + " ");
                   }
               }
           }
       }

       Arrays.fill(배열명, 값)

       → 배열 내부의 모든 값을 하나로 초기화 하는 메소드.

       Arrays.fill(isPrime, true); → isPrime의 모든 인덱스의 값을 true로 초기화 함.

       소수는 true, 소수가 아닌 수는 false → 초기에는 모든 수를 소수로 가정!

       for문을 i * i부터 시작하는 이유

       i * i 이전의 값은 이미 지워졌기 때문이다.

       예시

       i = 2일 때:

       • 2의 배수는 4, 6, 8, 10, 12, ...

         i = 3일 때:

       • 3의 배수는 6, 9, 12, 15, ...

         3 * 3 이전의 수는 3 * 2이다.

         하지만 이전에 2의 배수를 지우는 과정에서 2 * 3으로 인해 지워졌다.

         4일 경우를 확인해 보면, 4 * 2, 4 * 3은 2와 3의 배수를 지우는 과정인 2 * 4, 3 * 4에서 지워졌다.

         5일 경우를 확인해 보면, 5 * 4, 5 * 3, 5 * 2 는 모두 2와 3과 4의 배수를 지우는 과정인 2 * 5, 3 * 5, 4 * 5 에서 지워졌다.

         결론

         i * i 미만의 값은 모두 이전 과정에서 지워졌기 때문에 반복문의 시작 값을 i * i로 설정한다.

         시간복잡도: O(Nlog(log N))

    ✅위의 에라토스테네스의 체를 가지고 코드를 구현해보자

    import java.util.Arrays;
    
    class Solution {
        public int solution(int[] nums) {
            int answer = 0;
            
            // 0. 오름차순 정렬
            Arrays.sort(nums);
    
            // 1. 합의 최댓값 구하기
            int n = nums.length;
            int maxSum = nums[n - 1] + nums[n - 2] + nums[n - 3];
    
            // 2. 에라토스테네스의 체로 소수 판별 배열 만들기
            boolean[] isPrime = new boolean[maxSum + 1];
            Arrays.fill(isPrime, true); // 일단 전부 소수라고 가정
            isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님
    
            for (int i = 2; i * i <= maxSum; i++) {
                if (isPrime[i]) {
                    for (int j = i * i; j <= maxSum; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
    
            // 3. 3개 조합 만들기 + 소수 판별
            for (int i = 0; i < n - 2; i++) {
                for (int j = i + 1; j < n - 1; j++) {
                    for (int k = j + 1; k < n; k++) {
                        int sum = nums[i] + nums[j] + nums[k];
                        if (isPrime[sum]) {
                            answer++;
                        }
                    }
                }
            }
    
            return answer;
        }
    }
    

    기존 코드와 시간 복잡도 비교

  1. 기존 코드

     • 3중첩 for문: O(N^3)
     • 소수 판별: O(√N)

  2. 에라토스테네스의 체를 사용한 코드
     - 3중첩 for문: O(N^3)
     - 에라토스테네스의 체 만들기: O(Nlog(log N))
     - 소수 판별: O(1)

     N이 커지게 되면 에라토스테네스의 체 방식이 시간 복잡도가 효율적이다.

코드 구현

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int sum = 0;

        for(int i = 0; i < nums.length - 2; i++) {
            for(int j = i + 1; j < nums.length - 1; j++) {
                for(int k = j + 1; k < nums.length; k++) {
                    sum = nums[i] + nums[j] + nums[k];
                    
                    boolean isBreak = false;
                    
                    // 소수 판단
                    for(int l = 2; l <= Math.sqrt(sum); l++) {
                        if(sum % l == 0) {
                            isBreak = true;
                            break;
                        }
                    }
                    
                    if(!isBreak) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
}

배우게 된 점

1. Math.sqrt() 사용법에 대해 알 수 있었다.
2. 소수를 판별하는 에라토스테네스의 체를 익힐 수 있었다.
3. 문제에 접근하고 떠올린 방법을 코드로 구현하는 능력을 기를 수 있었다.