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

안녕하세요. 민쯔입니다.😊
이번 주에는 소수 만들기 문제를 풀어봤습니다.
소수 만들기 문제는 두 개 뽑아서 더하기 문제랑 비슷해서 두 개 뽑아서 더하기 문제를 풀었으면 쉽게 풀었을 것 같아요.

그럼 해결방안에 대해 설명하겠습니다.

문제 설명

function solution(nums) {
    var answer = 0;
    let sumArr = [];
    
    // 3개의 수를 더했을 때    
    for(let a = 0; a < nums.length; a++){
        for(let b = 0; b < nums.length-a-1; b++){
            for(let c =0; c < nums.length-a-b-2; c++){
                let numA = nums[a];
                let numB = nums[a+b+1];
                let numC = nums[a+b+c+2];
                let sum = numA + numB + numC;
                sumArr.push(sum);   
            }
        }
    }      
    
    // 소수가 되는 경우의 개수 구하기    
    for(let i of sumArr) {
       let isPrime = true;
       for(let j = 2; j <=  Math.sqrt(i); j++) {
          if(i % j == 0) isPrime = false;
       }
       if(isPrime) answer++;
    }
    return answer;
}

 

3개의 수를 더했을 때

// 3개의 수를 더했을 때    
for(let a = 0; a < nums.length; a++){
	for(let b = 0; b < nums.length-a-1; b++){
		for(let c =0; c < nums.length-a-b-2; c++){
			let numA = nums[a];
			let numB = nums[a+b+1];
			let numC = nums[a+b+c+2];
			let sum = numA + numB + numC;
			sumArr.push(sum);   
		}
	}
}

먼저 3개의 수의 합을 구했습니다.
저는 간단하게 for문을 3번 써서 구했는데요.
주어진 숫자 중 3개의 수라고 하면

• 첫번째 for문은 numA(첫번째 숫자)
• 두번째 for문은 numB(두번째 숫자)
• 세번째 for문은 numC(세번째 숫자)

로 구했습니다.
예 #1로 설명을 하자면
nums [1,2,3,4] 이 있다고 하면 3가지 숫자를 뽑을 경우의 수를 구하면

• 1, 2, 3
• 1, 2, 4
• 1, 3, 4
• 2, 3, 4

이렇게 4가지 경우가 있는데 이걸 보시면
첫번째 자리가 1이면 다음 두번째 수는 1이 아닌 다른 수만 가능합니다.
첫번째 자리가 1이고, 두번쨰 자리가 2이면 세번째 수는 1, 2가 아닌 다른 수를 사용해야 됩니다.
즉 앞에서 사용한 수는 쓸 수가 없는 거죠.
이 말을 for문으로 작성을 한 겁니다.

위의 코드를 예제 #1 적용해서 설명하자면
for(let a = 0; a < nums.length; a++) -> for(let a = 0; a < 4; a++) -> a는 0, 1, 2, 3 가능

a=0일 경우
1, 2, 3

• a=0
• let numA = nums[a]; -> let numA = nums[0]; -> let numA = 1;

for(let b = 0; b < nums.length-a-1; b++) -> for(let b = 0; b < 4-0-1; b++)
-> for(let b = 0; b < 3 ; b++) -> b는 0, 1, 2 가능

• b=0
• let numB = nums[a+b+1]; -> let numB = nums[0+0+1]; -> let numB = nums[1]; -> let numB = 2;

for(let c =0; c < nums.length-a-b-2; c++) -> for(let c =0; c < 4-0-0-2; c++)
-> for(let c =0; c < 2; c++) -> c는 0, 1 가능

• c=0
• let numC = nums[a+b+c+2]; -> let numC = nums[0+0+0+2]; -> let numC = nums[2]; -> let numC = 3;

numA, numB, numC -> 1, 2, 3

1, 2, 4

• a=0
• let numA = 1;

for(let b = 0; b < 4-0-1; b++) -> b는 0, 1, 2 가능

• b=0
• let numB = nums[a+b+1]; -> let numB = 2;

for(let c =0; c < 4-0-0-2; c++) -> c는 0, 1 가능

• c=1
• let numC = nums[a+b+c+2]; -> let numC = nums[0+0+1+2]; -> let numC = nums[3]; -> let numC = 4;

numA, numB, numC -> 1, 2, 4

1, 3, 4

• a=0
• let numA = 1;

for(let b = 0; b < 4-0-1; b++) -> b는 0, 1, 2 가능

• b=1
• let numB = nums[a+b+1]; -> let numB = nums[0+1+1]; -> let numB = nums[2]; -> let numB = 3;

for(let c =0; c < nums.length-a-b-2; c++) -> for(let c =0; c < 4-0-1-2; c++)
-> for(let c =0; c < 1; c++) -> c는 0 가능

• c=0
• let numC = nums[a+b+c+2]; -> let numC = nums[0+1+0+2]; -> let numC = nums[3]; -> let numC = 4;

numA, numB, numC -> 1, 3, 4

1, 4, X

• a=0
• let numA = 1;

for(let b = 0; b < 4-0-1; b++) -> b는 0, 1, 2 가능

• b=2
• let numB = nums[a+b+1]; -> let numB = nums[0+2+1]; -> let numB = nums[3]; -> let numB = 4;

for(let c =0; c < nums.length-a-b-2; c++) -> for(let c =0; c < 4-0-2-2; c++)
-> for(let c =0; c < 0; c++) -> c는 없음으로 다음 순서인 a=1 실행

a=1일 경우
2, 3, 4

• a=1
• let numA = nums[a]; -> let numA = nums[1]; -> let numA = 2;

for(let b = 0; b < nums.length-a-1; b++) -> for(let b = 0; b < 4-1-1; b++)
-> for(let b = 0; b < 2 ; b++) -> b는 0, 1 가능

• b=0
• let numB = nums[a+b+1]; -> let numB = nums[1+0+1]; -> let numB = nums[2]; -> let numB = 3;

for(let c =0; c < nums.length-a-b-2; c++) -> for(let c =0; c < 4-1-0-2; c++)
-> for(let c =0; c < 1; c++) -> c는 0 가능

• c=0
• let numC = nums[a+b+c+2]; -> let numC = nums[1+0+0+2]; -> let numC = nums[3]; -> let numC = 4;

numA, numB, numC -> 2, 3, 4

2, 4, X

• a=1
• let numA = nums[a]; -> let numA = 2;

for(let b = 0; b < nums.length-a-1; b++) -> b는 0, 1 가능

• b=1
• let numB = nums[a+b+1]; -> let numB = nums[1+1+1]; -> let numB = nums[3]; -> let numB = 4;

for(let c =0; c < nums.length-a-b-2; c++) -> for(let c =0; c < 4-1-1-2; c++)
-> for(let c =0; c < 0; c++) -> c는 없음으로 다음 순서인 a=2 실행

• c=0
• let numC = nums[a+b+c+2]; -> let numC = nums[1+0+0+2]; -> let numC = nums[3]; -> let numC = 4;

numA, numB, numC -> 2, 3, 4

a=2일 경우
3, 4, X

• a=2
• let numA = nums[a]; -> let numA = nums[2]; -> let numA = 3;

for(let b = 0; b < nums.length-a-1; b++) -> for(let b = 0; b < 4-2-1; b++)
-> for(let b = 0; b < 1 ; b++) -> b는 0 가능

• b=0
• let numB = nums[a+b+1]; -> let numB = nums[2+0+1]; -> let numB = nums[3]; -> let numB = 4;

for(let c =0; c < nums.length-a-b-2; c++) -> for(let c =0; c < 4-2-0-2; c++)
-> for(let c =0; c < 0; c++) -> c는 없음으로 다음 순서인 a=3 실행

a=3일 경우
4, X, X

• a=3
• let numA = nums[a]; -> let numA = nums[3]; -> let numA = 4;

for(let b = 0; b < nums.length-a-1; b++) -> for(let b = 0; b < 4-3-1; b++)
-> for(let b = 0; b < 0 ; b++) -> b는 없음으로 for문 끝

여기서
let sum = numA + numB + numC; 에 해당하는 4가지를 계산하면

• 1 + 2 + 3 = 6
• 1 + 2 + 4 = 7
• 1 + 3 + 4 = 8
• 2 + 3 + 4 = 9

sum값을 push를 사용하여 sumArr에 담아줬습니다.

여기서 참고로 예제 #1은 중복되는 수가 없는데 예제 #2은 중복되는 수가 있어요.
3개의 수의 합이 중복되는 수가 있다 해도 중복제거하시면 안 됩니다!! 그러면 제출 후 채점하기 통과 못합니다.

소수가 되는 경우의 개수 구하기

// 소수가 되는 경우의 개수 구하기    
for(let i of sumArr) {
	let isPrime = true;
	for(let j = 2; j <=  Math.sqrt(i); j++) {
		if(i % j == 0) isPrime = false;
	}
	if(isPrime) answer++;
}
return answer;

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.
그래서 보통 알고 있는 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29....인데요.

코드로 소수를 구하기 위해서는 % 나머지 값으로 구하면 됩니다.

1. 자신이 해당한 수 % (2 ~ 자신이 해당한 수)
2. 자신이 해당한 수 % (2 ~ 자신이 해당한 수의 제곱근)

저는 여기서 2번 방법을 사용했습니다.
2번 방법이 1번보다 더 짧게 계산하기 때문에 사용했습니다.

제곱근은 Math.sqrt()를 사용하면 구할 수 있습니다.

• Math.sqrt(4) -> 2
• Math.sqrt(9) -> 3

for(let i of sumArr) : for of을 사용하여 3개의 수의 합을 나오게 했습니다.
예제 #1로 설명하자면

• sumArr[6, 7, 8, 9]
• for(let i of sumArr) -> i는 6, 7, 8, 9

i = 6 일 경우 (소수가 아닐 경우)
for(let j = 2; j <= Math.sqrt(i); j++) -> for(let j = 2; j <= Math.sqrt(6); j++)
-> for(let j = 2; j <= √6; j++) -> for(let j = 2; j <= 2.4494~; j++) -> j는 2 가능

• j = 2
• if(i % j == 0) -> if(6 % 2 == 0) -> true
• let isPrime = true; -> isPrime = false;

if(isPrime) answer++;는 isPrime가 true일때만 작동되게 했으므로
i=6일 때 isPrime = false 임으로 if문을 실행할 수 없습니다.

i = 7 일 경우 (소수일 경우)
for(let j = 2; j <= Math.sqrt(i); j++) -> for(let j = 2; j <= Math.sqrt(7); j++)
-> for(let j = 2; j <= √7; j++) -> for(let j = 2; j <= 2.6457~; j++) -> j는 2 가능

• j = 2
• if(i % j == 0) -> if(7 % 2 == 0) -> false;
• let isPrime = true; 그대로

if(isPrime) answer++;는 isPrime가 true일때만 작동되게 했으므로
i=7일 때 isPrime = true 임으로 if문을 실행하고 answer++이 됩니다.

여기까지 소수 만들기 해결방안이었습니다.👏