2023.04.18 TIL - 소수 만들기

[Problem]

소수 만들기

 

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

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

 

@ 입출력 예
nums result
[1,2,3,4] 1
[1,2,7,6,4] 4
입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

@ 입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

[Try]

<첫 접근>

1. 배열에서 무작위로 3개를 뽑는다.(const randomArr = Math.floor(Math.random() * array.length) 이용)
2. 3개를 뽑아 합을 해서 소수인지를 판별한다.
3. 소수인 개수를 count한다.

<첫 접근에 대한 문제점>

==> 랜덤으로 뽑는 방법을 선택할 때 무작위로 추출하는 데 다음에 뽑히는 요소가 겹치는 경우가 발생한다. 이를 처리할 수 있는 로직이 필요한데 값을 3개를 추출할 때 다른 반복문을 3개가 필요해 보인다. 이런 3개 반복문을 연결할 필요도 있어 보인다.

 

==> 접근과 문제점 파악 부분을 통해 3개의 for문을 중첩할 필요가 있어 보였다. Time complexity가 문제가 있어 보이지만 현재 생각 방법으로는 for문을 3개 겹치는게 최선이라 생각이 들었다.

 

[Solution]

function solution(nums) {
    let answer = 0
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                const sum = nums[i] + nums[j] + nums[k]	// 값을 3개를 뽑아 합
                if (primeNum(sum)) answer++
            }
        }
    }
    return answer
}

// 소수를 판별 함수
function primeNum(sum) {
    for (let a = 2; a < sum; a++) {
        if (sum % a == 0) return false;
    }
    return true;
}

검색을 통해 소수를 판별하는 함수를 따로 만들 필요가 있어 보였다. 따라서 primeNum으로 함수를 열어줬다.

 

[Conclusion]

<다른 사람이 작성한 코드>

function solution(nums) {
  const combis = getCombination(nums, 3);
  const elementSum = getElmentSum(combis);
  const prime = getPrimeNumList(Math.max(...elementSum));

  return elementSum.filter(el => prime[el] !== 0).length; 
}

function getCombination(arr, len = arr.length) {
  if (len === 1) return arr.map(el => [el]);

  const combis = [];

  arr.forEach((curr, idx) => {
    const smallerCombis = getCombination(arr.slice(idx + 1), len - 1);

    smallerCombis.forEach((smallerCombi) => {
      combis.push([curr, ...smallerCombi]);
    });

  });

  return combis;
}

function getElmentSum(comb) {
  return comb.map(el => el.reduce((a,b)=>a+b));
}

function getPrimeNumList(num) {
  const prime = [];

  for(let i = 2; i <= num; i += 1) {
    prime.push(i);
  }

  for(let i = 2; i <= Math.sqrt(num); i += 1) {
    if(prime[i] === 0) continue;

    for(let j = i + i; j <= num; j += i) {
      prime[j] = 0;
    }
  }

  return prime;
}

첫 접근으로 생각한 부분과 매우 비슷한 코드 작성이라 가지고 왔다. for문을 여러번 사용하고 함수를 따로 3개를 만들어준 부분은 생각 못했지만, 생각했던 방향성과는 비슷해 보인다.  검색을 통해 조금 쉬운 방법으로 문제를 해결했지만 위에 다른 분이 작성 코드처럼 처음 생각했던 방법으로 코드를 다시 작성해보는 것도 나에게 도움이 될 것이라 생각된다. 어렵겠지만 한번 더 작성해야 겠다.