[Java] 프로그래머스(level-1) - 소수 만들기

입출력 예시

Input-1
[1, 2, 3, 4]
Output-1
1

Input-2
[1, 2, 7, 6, 4]
Output-2
4

문제 풀이

조합을 활용해 nums배열 중 3개의 원소를 뽑아야 한다.
핵심은 뽑은 원소가 중복되면 안되기 때문에 앞에서부터 차례대로 원소를 뽑아보는 것이다.

3개를 뽑는다고 정해놨기 때문에 단순하게 반복문을 3번 돌면 된다.

for(int i=0; i<n; i++) {
    for(int j=i+1; j<n; j++) {
        for(int k=j+1; k<n; k++){
            int sum = nums[i]+nums[j]+nums[k];
            if(isPrime(sum) == 2) answer++;
        }
    }
}

위 코드를 보면
첫번째 반복문에서 첫번째 수를 고르고 두번째 반복문에서 뽑은 수를 제외한 다음 수를 고른다.
세번째 반복문에서 또 뽑은 수를 제외한 다음 수를 골라 nums 배열의 원소에서 3가지로 고른 경우의 수를 구할 수 있다.

작성 코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        // int[] arr = {1,2,7,6,4};
        long start = System.currentTimeMillis();
        solution(arr);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int solution(int[] nums) {
        int answer = 0;
        int n = nums.length;

        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                for(int k=j+1; k<n; k++){
                    int sum = nums[i]+nums[j]+nums[k];
                    if(isPrime(sum) == 2) answer++;
                }
            }
        }
        return answer;
    }

    public static int isPrime(int num) {
        int count = 0;
        for(int i = 1; i <= num; i++) {
            if(num % i == 0) count += 1;
            if(count >= 3) return count;
        }   
        return count;
    }
}

회고

• 순열이나 조합에 대한 공부가 부족하다고 느꼈고, 백트래킹이나 재귀함수로 구현하는 복습을 꼭 해보도록 하자.