[프로그래머스] 소수만들기 java 자바

문제

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

풀이

간단한 문제다. 숫자 세개 뽑을 때 인덱스만 좀 신경써주자.

나는 옛날에 풀었던 시간복잡도에 걸리지 않게 소수 체크하는 방법을 복습할겸 그 때 풀었던 방법으로 풀었는데

이 문제에선 그냥 일반적인 방법대로 풀어도 괜찮다. 그냥 일반적인 방법은 아래와 같다. 일반적인 방법은 for문에서 조건절이 i<n이고 앞서 말한 방법에서는 i*i<=n임에 유의하자.

public static boolean isPrime(int n) {
		boolean test=true;
		
		for(int i=2;i<n;i++) {
			if(n>1&&n%i==0) {
				test=false;
				break;
			}
		}
        
        if(n<=1) test=false;
		
		return test;
	}

 

코드

package Level1;

public class 소수만들기 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(solution(new int[] {1,2,3,4}));
	}
	
	public static int solution(int [] nums) {
		int answer=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++) {
					int sum=nums[i]+nums[j]+nums[k];
					if(isPrime(sum)) {
						answer++;
					}
				}
			}
		}
		
		return answer;
	}
	
	public static boolean isPrime(int n) {
		boolean test=true;
		
		for(int i=2;i*i<=n;i++) {
			if(n>1&&n%i==0) {
				test=false;
				break;
			}
		}
		
		if(n<=1) test=false;
		
		return test;
	}
	
}