prgms.12977 - 소수의 개수

문제 분석

  • 문제 유형 : 브루트 포스
  • 걸린 시간 : 24분 32초
  • 풀이 전략 : nums에 있는 여러 개의 수 중에서 서로 다른 3개만 골라서 -> 합을 구한 뒤 -> 소수인지 판별하고, 소수이면 answer++
  • 걸렸던 부분 : 여러 개의 수 중에서 3개가 중복되지 않게 골라야하는데 단순히 반복문을 돌아서는 구할 수 없다. 그래서 반복문으로 바로 떠오르지 않아 nC3조합을 구하는 방법으로 구현하였다.

나의 풀이

combination 메서드를 구현하여 nC3을 돌리고 그 안에서 isPrime 메서드를 호출하여 소수여부를 판단한다. 소수이면 answer++를 수행한다.

combination을 직접 구현하는게 아직 익숙하지 않아서 웹 상에서 참조하여 수정했다. 자바에서는 반드시 암기해야할 부분이다.

  • 참조 링크 : https://bcp0109.tistory.com/15
class Solution {
    int answer = 0;

    public int solution(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];

        combination(nums, visited, 0, n, 3);

        return answer;
    }

    private void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            int sum = sum(arr, visited, n);
            if (isPrime(sum)) answer++;
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
    }

    private int sum(int[] arr, boolean[] visited, int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                sum += arr[i];
            }
        }
        return sum;
    }
  
    private boolean isPrime(int num) {
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

다른 사람의 풀이

내가 막혔던 부분인 3중 for문에서 인덱스를 0부터 시작하는게 아니라 각 바깥 반복문 인덱스 + 1로 시작하여 끝 부분에서는 겹치지않게 그만큼 빼준다.

i : 0 1 2 3 4 5 6 7 8

j : 1 2 3 4 5 6 7 8 9

k : 2 3 4 5 6 7 8 9 10

3개라는 제한이 있기 때문에 3중 for문으로 충분히 해결 가능하지만 무수히 많은 수를 검사해야하거나 변수로 주어진다면 조합이나 재귀를 이용한 방법으로 해결하는 것이 바람직할 것이다.

import java.util.Arrays;

class Solution {
    public int solution(int[] nums) {
        int ans = 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 ++ ){
                    if(isPrime(nums[i] + nums[j] + nums[k])){
                        ans += 1;  
                    } 
                }
            }
        }
        return ans;
    }
    public Boolean isPrime(int num){
        int cnt = 0;
        for(int i = 1; i <= (int)Math.sqrt(num); i ++){
            if(num % i == 0) cnt += 1; 
        }
        return cnt == 1;
    }
}