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

2021.11.01에 푼 문제입니다.

 

소수 만들기 문제는 두 개 뽑아서 더하기 문제랑 비슷해서 두 개 뽑아서 더하기 문제를 풀었으면 쉽게 풀었을 것 같아요.

---

해결방안

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;
}

 

해결방안 순서

1. 중첩 for문을 3개를 써주어 3개의 수를 더했을 때 나온 값을 sumArr배열에 담아준다.
2. 3개의 수를 더한 값을 담아준 sumArr배열 원소 중 소수가 되는 경우의 개수를 세기

 

1단계. 중첩 for문을 3개를 써주어 3개의 수를 더했을 때 나온 값을 sumArr배열에 담아준다.

먼저 nums배열에 있는 숫자 중 3개의 수를 더했을 때 나오는 모든 수를 구해보았는데요.

저는 for문 3개를 중첩해서 써주었습니다.

원래 중첩 for문을 많이 써주면 안 되는데😓 이 방법밖에는 생각이 안 나서 이렇게 풀어주었습니다.

 

3개의 수를 더해줄때 중복되는 숫자를 더해주면 안 됩니다.

여기 입출력 예만 봐도 같은 3개의 수 중에서 겹치는 숫자가 없죠?

그래서 이점을 참고해서 코드를 짜주어야 되는데요.

 

테스트 1을 예시로 설명하자면 nums=[1, 2, 3, 4]

자세히 설명하자면

첫 번째 자리가 1이면 다음 두 번째 수는 1이 아닌 다른 수만 가능합니다.

• 1, ?(2, 3, 4)

첫 번째 자리가 1이고, 두 번째 자리가 2이면 세 번째 수는 1, 2가 아닌 다른 수를 사용해야 됩니다.

• 1, 2, ?(3, 4)

즉 앞에서 사용한 수는 쓸 수가 없는 거죠.

 

그래서 테스트 1에서 나올 수 있는 3개의 수는

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

총 4가지가 됩니다.

 

// 1단계. 중첩 for문을 3개를 써주어 3개의 수를 더했을 때 나온 값을 sumArr배열에 담아준다.
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);   
		}
	}
}

• let numA = nums[a]; : 첫 번째 숫자
• let numB = nums[a+b+1]; : 두 번째 숫자
  -> nums[a+b+1]로 한 이유는 a, b가 0일 경우 첫 번째 수와 두 번째 수가 같은 숫자가 되면 안돼서 a+b+1로 해주었습니다.
• let numC = nums[a+b+c+2]; : 세 번째 숫자
  -> nums[a+b+c+2]로 한 이유는 numB와 똑같이 a, b, c 모두가 0이면 첫 번째, 두 번째 수가 중복이 되기 때문에 해주었고, numB에서 +1를 해주었기 때문에 그다음의 숫자를 쓰기 위해 +2를 해주었습니다.

 

테스트 1을 예시로 설명 nums=[1, 2, 3, 4]

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

 

a=0 일 때

a=0 일 때

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

b = 0 일 때

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

c = 0 일 때

let numA = nums[a] = nums[0] = nums[0] = 1

let numB = nums[a+b+1] = nums[0+0+1] = nums[1] = 2

let numC = nums[a+b+C+2] = nums[0+0+0+2] = nums[2] = 3

1, 2, 3

let sum = numA + numB + numC; -> let sum = 1 + 2 + 3 = 6

sumArr[6]

 

a=0 일 때

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

b = 0 일 때

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

c = 1 일 때

let numA = nums[a] = nums[0] = nums[0] = 1

let numB = nums[a+b+1] = nums[0+0+1] = nums[1] = 2

let numC = nums[a+b+C+2] = nums[0+0+1+2] = nums[3] = 4

1, 2, 4

let sum = numA + numB + numC; -> let sum = 1 + 2 + 4 = 7

sumArr[6, 7]

 

a=0 일 때

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

b = 1 일 때

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

c = 0 일 때

let numA = nums[a] = nums[0] = nums[0] = 1

let numB = nums[a+b+1] = nums[0+1+1] = nums[2] = 3

let numC = nums[a+b+C+2] = nums[0+1+0+2] = nums[3] = 4

1, 3, 4

let sum = numA + numB + numC; -> let sum = 1 + 3 + 4 = 8

sumArr[6, 7, 8]

 

a=0 일 때

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

b = 2일 때

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

세 번째 for문을 실행할 수 없음

다음 a=1로 넘어감

 

 

a=1 일 때

a=1 일 때

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

b = 0 일 때

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

c = 0 일 때

let numA = nums[a] = nums[1] = nums[1] = 2

let numB = nums[a+b+1] = nums[1+0+1] = nums[2] = 3

let numC = nums[a+b+C+2] = nums[1+0+0+2] = nums[3] = 4

2, 3, 4

let sum = numA + numB + numC; -> let sum = 2 + 3 + 4 = 9

sumArr[6, 7, 8, 9]

 

a=1 일 때

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

b = 1 일 때

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

c = 0 일 때

세 번째 for문을 실행할 수 없음

다음 a=2로 넘어감

 

a=2 일 때

a=2 일 때

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

b = 0 일 때

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

c = 0 일 때

세 번째 for문을 실행할 수 없음

a=2까지만 가능하기 때문에

for(let a = 0; a < nums.length; a++) 구문 끝!!

 

테스트 1
nums = [1,2,3,4];
1, 2, 3 = 6
1, 2, 4 = 7
1, 3, 4 = 8
2, 3, 4 = 9
sumArr = [6, 7, 8, 9];


테스트 2
nums = [1,2,7,6,4];
1, 2, 7 = 10
1, 2, 6 = 9
1, 2, 4 = 7
1, 7, 6 = 14
1, 7, 4 = 12
1, 6, 4 = 11
2, 7, 6 = 15
2, 7, 4 = 13
2, 6, 4 = 12
7, 6, 4 = 17
sumArr  = [10, 9, 7, 14, 12, 11, 15, 13, 12, 17]

 

 

2단계. 3개의 수를 더한 값을 담아준 sumArr배열 원소 중 소수가 되는 경우의 개수를 세기

sumArr배열 원소 중에서 소수가 되는 경우의 개수를 세기 위해 for... of문, for문, if문을 사용했는데요.

 

for... of문은 전에 블로그로 쓴 프로그래머스 예산문제에서 설명을 드려서 거기에서 쓴 블로그 그대로 들고 오겠습니다.

MDN Web Docs
for...of 명령문은 반복 가능한 객체 (Array, Map, Set, String, TypedArray, arguments 객체 등을 포함)에 대해서 반복하고 각 개별 속성 값에 대해 실행되는 문이 있는 사용자 정의 반복 후크를 호출하는 루프를 생성합니다.

구문 :

for (variable of iterable) {
  statement
}

• variable : 각 반복에 서로 다른 속성 값이 variable에 할당됩니다.
• iterable : 반복되는 열거가능(enumerable)한 속성이 있는 객체.

MDN에서는 이렇게 설명하지만 간단하게 설명하자면

for... of는 배열 값 순환이라 하면 쉽게 이해하실 수 있습니다.

const arr = ['a', 'b', 'c'];

for (const element of arr) {
  console.log(element);
}
// "a"
// "b"
// "b"

 

// 2단계. 3개의 수를 더한 값을 담아준 sumArr배열 원소 중 소수가 되는 경우의 개수를 세기
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;

 

for(let i of sumArr)

• 테스트1(nums = [1,2,3,4])이면 sumArr = [6, 7, 8, 9] 입니다.
• i는 6, 7, 8, 9 차례로 나옴

여기서 for...of문을 사용한 이유는

1단계에서 3개의 수를 더했을 때 나온 값을 sumArr배열 담아주었는데

sumArr배열 원소가 소수인지 확인하기 위해서는 원소를 반복하는 for...of문이 사용하기 좋기 때문입니다.

 

 

이제 for...of문 안에 소수를 구하는 코드가 들어가야 되는데요.

그전에 소수가 뭔지 간단하게 설명하자면

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

 

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

예를 들면 "13이라는 숫자가 소수인지 알고 싶다."라고 한다면

13이 소수이기 위해서는 13의 약수가 1, 13 이 두 가지 되는데

• 13 % j == 0

j가 (2~12)까지 나누는데 나머지가 0이 나오면 소수가 아니라는 거겠죠?

(여기서 1, 13을 제외한 이유는 모든 숫자가 1과 자기 자신을 나누면 나머지가 0이기 때문에 뺐습니다.)

• 13%2 == 0 -> false
• 13%3 == 0 -> false
• 13%4 == 0 -> false
• 13%5 == 0 -> false
• 13%6 == 0 -> false
• 13%7 == 0 -> false
• 13%8 == 0 -> false
• 13%9 == 0 -> false
• 13%10 == 0 -> false
• 13%11 == 0 -> false
• 13%12 == 0 -> false

이렇게 13은 소수라고 판명이 됩니다.

 

위에 설명한 내용을 코드로 쓴다면

// 13이 소수인지 확인
let isPrime1 = true;
for(let j = 2; j < 13; j++) {
    if(13 % j == 0) isPrime1 = false;
}
console.log(isPrime1); // true

// 15가 소수인지 확인
let isPrime1 = true;
for(let j = 2; j < 15; j++) {
    if(15 % j == 0) isPrime1 = false;
}
console.log(isPrime1); // false

이렇게 써도 되긴 하는데

이 방법 말고도 다른 방법이 더 효율적입니다.

 

소수를 구하는 방법

1. 자신이 해당한 수 % (2 ~ 자신이 해당한 수-1) -> 모든 수는 1과 자신은 약수로 가지고 있기 때문에
2. 자신이 해당한 수 % (2 ~ 자신이 해당한 수의 제곱근)

여기서 1번 방법은 위에서 설명한 방법이고

저는 2번 방법 사용해서 풀어주었습니다.

2번 방법을 사용한 이유는 만약 100이라는 큰 숫자의 약수를 구해야 될 경우

1번 방법을 사용한다면 1~100까지 다 계산해야 되잖아아요.

그러면 너무 비효율적이게 됩니다.

그래서 2번 방법을 사용하는데요.

 

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

2번 방법에 대해 설명하자면

먼저 제곱근을 구하는 Math.sqrt()에 대해 알아봅시다.

MDN Web Docs
Math.sqrt()
 함수는 숫자의 제곱근을 반환합니다.

문법 : Math.sqrt(x)

• x : 숫자

Math.sqrt(9); // 3
Math.sqrt(2); // 1.414213562373095

Math.sqrt(1);  // 1
Math.sqrt(0);  // 0
Math.sqrt(-1); // NaN

 

만약 "101이 소수인지 아닌지 알고 싶다."면

for(let j = 2; j <=  Math.sqrt(101); j++)

• Math.sqrt(101) = 10.0498756211

for(let j = 2; j <=  10.0498756211; j++) -> 2, 3, 4, 5, 6, 7, 8, 9, 10까지 반복

• 101 % 2 == 0 -> false;
• 101 % 3 == 0 -> false;
• 101 % 4 == 0 -> false;
• 101 % 5 == 0 -> false;
• 101 % 6 == 0 -> false;
• 101 % 7 == 0 -> false;
• 101 % 8 == 0 -> false;
• 101 % 9 == 0 -> false;
• 101 % 10 == 0 -> false;

101은 소수입니다.

(여기서 j <=  Math.sqrt(101); -> <=로 한 이유는 자기가 해당하는 수가 아닌 제곱근으로 바뀌어서 같다는 표시를 해주었습니다.)

1번 방법으로 했으면 2~100까지 나머지가 0인지 아닌지를 구했을 텐데 10번 만에 끝나다니...!!!

역시 머리를 써야 되나 봐요ㅋㅋ

 

 

for(let j = 2; j <=  Math.sqrt(i); j++) {
    if(i % j == 0) isPrime = false;
}

• Math.sqrt(i); : 제곱근
• for(let j = 2; j <=  Math.sqrt(i); j++) : 2부터 i의 제곱근까지 반복
• i % j == 0 : 소수를 구하는 코드
• if(i % j == 0) isPrime = false; : 만약 i 나누기 j의 나머지 값이 0이면 isPrime=true;를 false로 바꿔주기

if(isPrime) answer++;

• 만약 isPrime이 true일 때마다 answer에 +1 해주기

테스트 1
nums = [1,2,3,4];
sumArr = [6, 7, 8, 9];
7 -> 소수
1개


테스트 2
nums = [1,2,7,6,4];
sumArr  = [10, 9, 7, 14, 12, 11, 15, 13, 12, 17]
7, 11, 13, 17 -> 소수
4개

---

여기까지 프로그래머스 소수 만들기 해결방안에 대해 설명해보았습니다.