소수 만들기

문제 링크

처음 풀이

길이 3 이상의 배열 내 숫자 3개의 합이 소수인 경우의 수를 구하는 문제이다.
모든 경우의 수를 구해야 했기 때문에 for문을 3개 썼는데
이 풀이대로라면 만약 4개의 합을 구하는 문제였다면 4개를 써야 했을까 하는 생각이 들었다 (아찔)

forEach와 같은 고차 함수를 쓰고 싶었으나 i, j, k의 시작점을 자유롭게 조절하기에는 for문이 짱이어서 그냥 for문을 사용했다. 시간 복잡도가 N 3제곱이었는데 다행히 시간 초과가 뜨지 않았다.

[ 풀이법 ]

1. 소수인지 여부를 판별하는 isPrime 함수 선언
2. solution 함수: nums 배열을 1,2,3 / 1,2,4 ... 식으로 돌기 위한 for문 3개 선언

• for-i문: nums 배열 맨 처음 ~ 뒤에서 3번째
• for-j문: i+1번째 ~ 뒤에서 2번째
• for-k문: j+1번째 ~ 맨 마지막

3. for-k문 안에서 sum이 소수인지 판별(isPrime)
4. 매번 반복문이 끝날 때마다 sum에서 k번째, j번째 값을 빼주고 i문이 끝났을 때는 sum을 0으로 초기화

function isPrime(n) {
    if (n === 1) return false;
    
    if (n !== 2 && n % 2 === 0) return false;
    
    for (let i = 3; i <= Math.floor(Math.sqrt(n)); i += 2) {
        if (n % i === 0) return false;
    }
    
    return true;
}

function solution(nums) {
    let answer = 0;
    let sum  = 0;
    
    for (let i = 0; i < nums.length - 2; i++) {
        sum += nums[i];
        
        for (let j = i + 1; j < nums.length - 1; j++) {
            sum += nums[j];
            
            for (let k = j + 1; k < nums.length; k++) {
                sum += nums[k];
                
                if (isPrime(sum)) answer++;
                
                sum -= nums[k];
            }
            
            sum -= nums[j];
        }
        
        sum = 0;
    }
    
    return answer;
}

새로운 풀이

isPrime과 solution을 훨씬 간단하게 만든 풀이가 있었다.
아래 solution처럼 하면 매 반복문마다 j번째, k번째 값을 안 빼줘도 될 것 같다.
또 반복되는 nums.length도 변수화해서 재사용한 것도 더 좋았따.

다만 isPrime 함수는 길이가 좀 더 길어도 내 코드를 사용할 것 같다.
예외 처리가 더 많아서 좀 더 다양한 상황에서 early return이 가능하고
Math.sqrt 들어간 for문에서 sqrt 값이 될 때까지 '홀수'만 구해서 모든 수를 확인하는 아래의 isPrime보다 절반의 연산만으로 소수 여부 확인이 되기 때문이다.

solution 함수가 훨씬 간결해져서 좋았다.

function solution(nums) {
  let answer = 0;
  let len = nums.length; 

  for (let i = 0; i < len - 2; i++) {
    for (let j = i + 1; j < len - 1; j++) {
      for (let k = j + 1; k < len; k++) {
        if (isPrime(nums[i] + nums[j] + nums[k])) {
          answer++;
        }
      }
    }
  }
    
  return answer;
}

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

  return true;
}