[알고리즘] 브루트포스(자릿수의 합, 뒤집은 소수)

이번에 공부한 알고리즘 파트는 브루트포스(brute force)다.

✨ Brute force란?
▶️ 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져오는 알고리즘.

가능한 모든 경우의 수를 탐색하기 때문에 완전탐색이라고도 부른다.

💡자릿수의 합

N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력 하는 프로그램을 작성하세요. 자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 합니다. 만약 235 와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력해야 합니다.

처음 문제를 보고 생각한 방식은 toString()으로 문자로 타입을 바꾼 다음, split을 이용해 문자열을 잘게 쪼개서 각 자릿수를 더하는 방식이었다. 그런데 이 경우 문자가 된 자릿수들을 어떻게 더해줄지가 고민이었는데(덧셈을 위해 for문을 또 만드는 건 별로라는 생각이 들었다.) reduce로 해결할 수 있었다.

  for (let x of arr) {
    let sum = x
      .toString()
      .split("")
      .reduce((a, b) => a + Number(b), 0);
  }

처음부터 간단하게 정리하자면, 일단 max라는 가장 큰 수를 담을 변수를 선언한다. 그 다음 for-of문으로 배열을 돌며 각 자릿수의 합이 가장 큰 수를 발견하면 max에 그 수를 할당한다. 그 뒤 그 값을 return한다. 전체 코드는 다음과 같다.

function solution(n, arr) {
  let answer,
    max = Number.MIN_SAFE_INTEGER;
  for (let x of arr) {
    let sum = x
      .toString()
      .split("")
      .reduce((a, b) => a + Number(b), 0);
    if (sum > max) {
      max = sum;
      answer = x;
    } else if (sum === max) {
      if (x > answer) answer = x;
    }
  }
  return answer;
}

그런데 풀이를 보니 굳이 숫자->문자->숫자 이렇게 타입을 계속 바꾸지 않고, 숫자를 그대로 사용하면서 해결하는 방식이 있었다. 바로 while문을 사용해서!

지난번 [알고리즘]10부제에 정리한 것처럼, 어떤 수든 10으로 나누면 나머지가 일의 자리 숫자가 되고, 그 앞의 숫자들이 몫이 된다. 그걸 이용해서 처음에 10을 나눠 일의 자리 숫자를 구한 다음 sum에 더하고, 몫을 다시 10으로 나눠 두번째 자릿수를 구한 다음 sum에 더하는 방식이다. (tmp라는 변수를 따로 선언한 것은 x의 값은 원래대로 남겨두기 위해서다.) while의 괄호 안에 (tmp)만 넣은 까닭은 괄호 안의 수가 0이 되면 자동으로 break되기 때문이다.

전체 코드는 아래와 같다.

function solution(n, arr) {
  let answer,
    max = Number.MIN_SAFE_INTEGER;
  for (let x of arr) {
    let sum = 0,
      tmp = x;
    while (tmp) {
      sum += tmp % 10;
      tmp = Math.floor(tmp / 10);
    }
    if (sum > max) {
      max = sum;
      answer = x;
    } else if (sum === max) {
      if (x > answer) answer = x;
    }
  }
  return answer;
}

💡 뒤집은 소수

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하 는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출 력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다.

소수를 보자마자 어? 에라토스테네스의 체? 했다. (들은 풍월만 많음)
근데 그 방식은 일단 프로그래머스의 소수 찾기 풀 때 더 공부해서 적용해보기로 하고, 오늘은 약수가 있는지 판별하는 방식으로 비교적 간단(?)하게 해결하기로.

무언가를 뒤집는 문제만 보면 split해서 reverse할 생각밖에 안하는 나는, 평소처럼 그 방식을 써서 뒤집었다. 뒤집는 거까진 쉬웠는데 어떻게 하면 소수를 판별할 수 있을까 하는 부분에서 막혔다. 풀이를 보니 for문을 돌며 i가 num의 약수이면 false를, 약수가 없으면 true를 반환하는 식으로 판별하는 방식이었다. 흥미로웠던 점은 n보다 작은 수를 모두 돌지 않고 제곱근까지만 확인해서 반복문의 범위를 줄이는 부분이었다.

또 split()을 사용하지 않고 while을 이용해 뒤집는 것도 인상적이었다.

let res = 0;
while (x) {
  let t = x % 10;
  res = res * 10 + t;
  x = parseInt(x / 10);
}

123을 예시로 들면, 123%10으로 나누면 아까 말했듯 일의 자리 숫자 3을 구할 수 있다. 그 다음 코드는, 처음엔 res가 0이기 때문에 10을 곱해도 0이고, 0에 3을 더하면 3이 된다. 123 나누기 10을 한 몫은 12가 된다. 그 12를 다시 x 값으로 할당하고, 12 나누기 10을 하면 일의 자리 숫자인 2가 t가 된다. 3*10+2를 하면 32가 된다. 이걸 다시 반복하면 321이 되는 것이다.

정리하자면, reverse()나 while문을 사용해서 숫자를 뒤집은 다음, isPrime이라는 함수를 만들어 소수인지 판별하면 해결할 수 있다.

최종 코드는 다음과 같다.

function isPrime(num) {
  if (num === 1) return false;
  for (let i = 2; i < parseInt(Math.sqrt(num)); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

function solution(arr) {
  let answer = [];
  for (let x of arr) {
    let res = Number(x.toString().split("").reverse().join(""));
    if (isPrime(res)) answer.push(res);
  }

  return answer;
}