문제 설명
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
- nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예
nums [1,2,3,4]
result 1
nums [1,2,7,6,4]
result 4
입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.
처음에 접근하기
왜인지.. 당연하단듯이 순열로 접근했다.. 사실은 중복을 무시해야 하는데..
그래서 다 적고 나서 아?! 그럼 그냥 나온 데이터들을 더 하면 하나의 값으로 귀결되니까 그게 겹치는 지 판단해서 소수인지 판단해서 set에 넣어두자 했지만..
import java.util.*;
class Solution {
static Set<Integer> set = new HashSet<>();
public int solution(int[] nums) {
doPermutation(nums, 0, 3);
return set.size();
}
public void doPermutation(int[] arr, int depth, int r){
if(depth==r){
int num = 0;
for(int i=0; i<r; i++){
num += arr[i];
}
if(!set.contains(num)){
if(isPrime(num)){
System.out.println(String.valueOf(num));
set.add(num);
}
}
}else{
for(int i=0; i<arr.length; i++){
swap(arr, depth, i);
doPermutation(arr, depth+1, r);
swap(arr, depth, i);
}
}
}
public void swap(int[] arr, int depth, int i){
int tmp = arr[i];
arr[i] = arr[depth];
arr[depth] = tmp;
}
public boolean isPrime(int num){
int sqrt_num = (int)Math.sqrt(num);
boolean flag = true;
if(num==2){
flag = true;
}else if(num%2==0 || num==1){
flag = false;
}else{
for(int i=3; i<=sqrt_num; i+=2){
if(num%i==0){
flag = false;
}
}
}
return flag;
}
}새롭게 접근하기
그래 새롭게 접근하다 생각하고 조합으로 갔다.
근데 너무 안풀리길래 보니까 순열과 조합을 쓰지도 않는 문제였다.
import java.util.*;
class Solution {
static Set<Integer> set = new HashSet<>();
public int solution(int[] nums) {
int n = nums.length;
boolean[] visited = new boolean[n];
doCombination(nums, visited, 0, 3);
return set.size();
}
public static void doCombination(int[] arr, boolean[] visited, int depth, int r){
if(r==0){
print(arr,visited);
return;
}
if(depth==arr.length){
return;
}else{
visited[depth] = true;
doCombination(arr, visited, depth+1, r-1);
visited[depth] = false;
doCombination(arr, visited, depth+1, r);
}
}
// 배열 출력
static void print(int[] arr, boolean[] visited) {
int result = 0;
for(int i = 0; i < arr.length; i++) {
if(visited[i] == true){
result += arr[i];
}
}
if(!set.contains(result)){
if(isPrime(result)){
set.add(result);
}
}
}
static boolean isPrime(int num){
int sqrt_num = (int)Math.sqrt(num);
boolean flag = true;
if(num==2){
flag = true;
}else if(num%2==0 || num==1){
flag = false;
}else{
for(int i=3; i<=sqrt_num; i+=2){
if(num%i==0){
flag = false;
}
}
}
return flag;
}
}정답 코드
3중 for문을 이용해서 푸는 거였다..
너무 어렵게 생각했나보다..
import java.util.*;
class Solution {
public int solution(int[] nums) {
int n = nums.length;
int count = 0;
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)){
count++;
}
}
}
}
return count;
}
static boolean isPrime(int num){
int sqrt_num = (int)Math.sqrt(num);
boolean flag = true;
if(num==2){
flag = true;
}else if(num%2==0 || num==1){
flag = false;
}else{
for(int i=3; i<=sqrt_num; i+=2){
if(num%i==0){
flag = false;
}
}
}
return flag;
}
}문제 출처
developer