Nyong's Blog
0%

210623_TIL(심심풀이 코딩 문제)

Posted on Edited on In ,

오늘 한 것

코딩 테스트 연습

소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한사항

  • n은 2이상 1000000이하의 자연수입니다.

나의 답

  • 에라토스테네스의 체를 참고하여 구현하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 성능 이슈
function firstSolution(n) {
  const min = Math.sqrt(n);
  const array = Array.from({ length: n - 1 }, (_, i) => i + 2);
  const minArr = Array.from({ length: min }, (_, i) => i + 1);
  let primeArr = array;

  for (let i = 0; i < minArr.length; i++) {
    let cnt = 0;
    for (let j = 1; j < minArr[i]; j++) {
      if (minArr[i] % j === 0) cnt++;
    }
    if (cnt === 1) {
      primeArr = primeArr.filter((v) => v % minArr[i] !== 0 || v === minArr[i]);
    }
  }

  return primeArr.length;
}

console.log(firstSolution(10)); // 4
console.log(firstSolution(5)); // 3
  • 처음에는 성능은 신경쓰지 않고 생각 나는데로 만들었다.
  • 효율성 검사에서 탈락했다. 지금 다시 보니 그럴만한 코드다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 성능 이슈
function secondSolution(n) {
  const min = Math.sqrt(n);
  const primeArr = [];

  let currentArr = Array.from({ length: n - 1 }, (_, i) => i + 2);

  const isPrime = (num) => {
    let cnt = 0;
    for (let i = 1; i < num; i++) {
      if (num % i === 0) cnt++;
    }

    return cnt === 1;
  };

  for (let i = 2; i < min; i++) {
    if (isPrime(i)) {
      primeArr.push(i);
      currentArr = currentArr.filter((v) => v % i !== 0);
    }
  }

  return [...primeArr, ...currentArr].length;
}

console.log(secondSolution(10)); // 4
console.log(secondSolution(5)); // 3
  • 나름 다시 고민해서 구현한 코드이다.
  • 소수 판별 함수를 따로 분리하고 filter()메서드로 소수의 배수들을 제한다.
  • 하지만 효율성 검사에서 역시나 실패했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const currentArr = Array.from({ length: n - 1 }, (_, i) => i + 2);

const isPrime = (num) => {
  let cnt = 0;
  for (let i = 1; i < num; i++) {
    if (num % i === 0) cnt++;
  }

  return cnt === 1;
};

for (let i = 2; i * i < n; i++) {
  if (isPrime(i)) {
    for (let j = i + i - 2; j < n; j += i) currentArr[j] = 0;
  }
}

return currentArr.filter((v) => v).length;

console.log(thirdSolution(10)); // 4
console.log(thirdSolution(5)); // 3
  • 정말 불필요한 부분은 최대한 제거했다. Math.sqrt() 메서드 조차도 뺴버렸다.
  • filter()로 순회하던 과정을 제거하고 for문을 통해 소수의 배수(j += i)로 순회하며 값 0을 할당한 뒤, 마지막에 filter()로 모든 0을 삭제한다.
  • 위 세가지 경우에 대해 성능을 검사해보니, 3번이 다른 두 경우보다 확실히 유의미한 성능차를 보였다.
  • 데이터가 커질 수록 자료구조를 순회하는 방법이 중요함을 다시금 느낀다.

소수 만들기

문제 설명

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

제한사항

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

나의 답

1
2
3
4
5
6
7
8
const isPrime = (num) => {
  let cnt = 0;
  for (let i = 1; i < num; i++) {
    if (num % i === 0) cnt++;
  }

  return cnt === 1;
};
  • 소수인지 판별하는 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 성능 우세
function solution(nums) {
  const odd = [];
  const even = [];

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] % 2 === 0) even.push(nums[i]);
    else odd.push(nums[i]);
  }

  let cnt = 0;

  for (let i = 0; i < even.length - 1; i++) {
    for (let j = i + 1; j < even.length; j++) {
      for (let k = 0; k < odd.length; k++) {
        if (isPrime(even[i] + even[j] + odd[k])) cnt++;
      }
    }
  }

  for (let i = 0; i < odd.length - 2; i++) {
    for (let j = i + 1; j < odd.length - 1; j++) {
      for (let k = j + 1; k < odd.length; k++) {
        if (isPrime(odd[i] + odd[j] + odd[k])) cnt++;
      }
    }
  }

  return cnt;
}

console.log(solution([1, 2, 3, 4])); // 1
console.log(solution([1, 2, 7, 6, 4])); // 4
  • 2를 제외한 모든 소수는 홀수이다. 본 문제에서는 중복되지 않는 1 이상의 세 수를 더한 소수를 구하기 때문에 발생 가능한 수 중 가장 작은 소수는 7이다.
  • 짝수와 홀수를 구분한 후, 홀수를 만들 수 있는 조합은 짝수 + 짝수 + 홀수와 홀수 + 홀수 + 홀수다.
  • 소수 발생 가능성이 있는 세수의 조합만을 계산하여 소수인지 판별한다.
  • 코드의 길이는 길지만 아래 단순 계산하는 코드보다 유의미하게 높은 성능 차이를 보였다. (1부터 100까지의 배열에서 약 2배의 성능 차이)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solution(nums) {
  let answer = 0;

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

  return answer;
}

console.log(solution([1, 2, 3, 4])); // 1
console.log(solution([1, 2, 7, 6, 4])); // 4
  • 모든 경우의 수를 생성한 후, 소수인지 판별하는 단순한 알고리즘이다.
  • 첫번째 경우보다 깔끔해보이지만 성능은 모든 경우의 수를 계산하기 떄문에 좋지 못하다.

약수의 개수와 덧셈

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

  • 1 ≤ left ≤ right ≤ 1,000

나의 답

1
2
3
4
5
6
7
8
9
10
11
12
13
function solution(left, right) {
  let sum = 0;

  for (let i = left; i <= right; i++) {
    let cnt = 0;
    for (let j = 1; j <= i; j++) {
      if (i % j === 0) cnt++;
    }
    cnt % 2 === 0 ? (sum += i) : (sum -= i);
  }

  return sum;
}
  • 삼항 조건 연산자가 편하긴 한데, if..else 문을 쓰는게 더 직관적인지 애매하다.
  • 쉬운 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solution(left, right) {
  let num = [];

  for (let i = left; i <= right; i++) {
    let cnt = 0;
    for (let j = 1; j <= i; j++) {
      if (i % j === 0) cnt++;
    }
    num.push([i, cnt]);
  }

  return num.reduce(
    (acc, cur) => (cur[1] % 2 === 0 ? acc + cur[0] : acc - cur[0]),
    0
  );
}
  • 배열 메서드 연습하고 싶어서 꼬아서 놀았다. 의미없다.

감탄한 타인의 답

1
2
3
4
5
6
7
8
9
10
11
function solution(left, right) {
  var answer = 0;
  for (let i = left; i <= right; i++) {
    if (Number.isInteger(Math.sqrt(i))) {
      answer -= i;
    } else {
      answer += i;
    }
  }
  return answer;
}
  • 제곱수(자연수를 제곱해 구해지는 수)의 약수 개수는 항상 홀수이다…같은 수를 두번 곱한 경우의 짝이 없는 약수가 1개 생기기 때문…수학 상식도 재밌다..

두 개 뽑아서 더하기

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

  • numbers의 길이는 2 이상 100 이하입니다.
    • numbers의 모든 수는 0 이상 100 이하입니다

나의 답

1
2
3
4
5
6
7
8
9
10
11
12
13
function solution(numbers) {
  const answer = [];

  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (i !== j) answer.push(numbers[i] + numbers[j]);
    }
  }

  return [...new Set(answer.sort((a, b) => a - b))];
}

console.log(solution([2, 1, 3, 4, 1])); // [2, 3, 4, 5, 6, 7]
  • 처음에는 j = 0으로 선언하여 불필요한 연산을 했다. 한번만 더 생각하자.

나누어 떨어지는 숫자 배열

문제 설명

array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

제한사항

  • arr은 자연수를 담은 배열입니다.
  • 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
  • divisor는 자연수입니다.
  • array는 길이 1 이상인 배열입니다.

나의 답

1
2
3
4
5
6
7
function solution(arr, divisor) {
  const answer = arr.filter((v) => v % divisor === 0).sort((a, b) => a - b);

  return answer.length ? answer : [-1];
}

console.log(solution([5, 9, 7, 10], 5)); // [5, 10]

3진법 뒤집기

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

  • n은 1 이상 100,000,000 이하인 자연수입니다.

나의 답

1
2
3
4
5
6
7
8
function solution(n) {
  const num = n.toString(3).split("").reverse().join("");
  // const num = [...n.toString(3)].reverse().join("");

  return parseInt(num, 3);
}

console.log(solution(45)); // 7
  • 내장함수로 간단히 해결
1
2
3
4
5
6
7
8
function solution(n) {
  const answer = [];
  while (n !== 0) {
    answer.unshift(n % 3);
    n = Math.floor(n / 3);
  }
  return answer.reduce((acc, v, i) => acc + v * Math.pow(3, i), 0);
}
  • 내장 함수 없이 계산도 가능하다.

출처: programmers

Nyong’s GitHub