문제 바로가기

나의 풀이

생각보다 오래 걸린 문제였다. 나는 우선 원소가 최대 998 999 1000이 선택될 경우를 생각하여 인덱스 2999까지 소수면 0, 소수가 아니면 1의 값을 가지도록 dp 테이블을 만들었다.

dp 테이블을 만들어준 이유는 3개 ~ 50개의 원소를 가진 nums 배열에서 만약 50개의 원소를 가지고 있다고 가정했을때, 50C3 의 경우의 수를 모두 소수인지 아닌지 판별해야 하는데, 일일이 계산한다면 시간복잡도에서 실패할 것이라는 생각이었다.

dp를 쓰지 않은 다른 사람의 풀이를 보니 4중 for문을 돌고 있다. 나의 풀이는 3중 for문이 2개 돌고 있기에 훨씬 효율적이라 볼 수 있을 것 같다.

내가 오래 걸렸던 곳은 의외로 조합을 생각해내는 과정이었는데, 파이썬에서는 조합 라이브러리가 존재하기 때문이었다. 조합 라이브러리가 따로 없는 자바에서는 직접 구성해야하는데 실패하였고, 그냥 3중 for문을 돌리면서 일일이 더해주는 식으로 하였다.

(원래 원했던 것은 nums.length와 조합에서 선택할 개수를 인수로 넣으면 2차원 배열식으로 인덱스 번호 조합이 반환되는 함수를 만들고, iteration을 돌면서 그 인덱스 조합에 해당하는 nums 값들을 더해서 dp테이블의 값이 0인지 확인하고 싶었다.)

자바에서 조합 및 순열을 구성하는 메서드는 공부하여 추후 포스팅을 해야겠다.

import java.util.*;

class Solution {
    public static int solution(int[] nums) {
        int[] dp = new int[3000];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < 1500; i++) {
            for (int j = 2; j < 1500; j++) {
                if (i * j >= 3000) {
                    break;
                }
                dp[i * j] = 1;
            }
        }

        List<Integer> result = new ArrayList<>();
        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++) {
                    result.add(nums[i] + nums[j] + nums[k]);
                }
            }
        }

        int answer = 0;
        for (Integer integer : result) {
            if (dp[integer] == 0) {
                answer += 1;
            }
        }
        return answer;
    }
}