- 프로그래머스 - 소수 만들기2025년 01월 14일
- redpome
- 작성자
- 2025.01.14.:17
데일리 알고리즘을 풀면서 느끼는 것은 절망뿐이다.
오늘의 문제다.
https://school.programmers.co.kr/learn/courses/30/lessons/12977
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
소수를 판별하는 문제다. 문제를 요약하자면 다음과 같다.
- 숫자가 담긴 배열이 매개변수로 넘겨진다.
- 숫자가 담긴 배열에서 서로 다른 3개의 수를 뽑아 합한다.
- 합한 수가 소수임을 판별하고 그런 수들이 몇 개인지 반환한다.
이제는 검색을 통해 다른 사람들의 풀이를 보고 지피티의 도움을 받아 힌트만 받아서 풀도록 했다.
문제를 풀면서 가급적 하나의 함수로 반환하는 것이 좋은지 아니면 그냥 내 맘대로 양식을 깨부숴도 되는지 모르겠다.
일단 코드는 다음과 같다.
function solution(nums) { let reult = 0; let count = 0; //배열에서 가능한 3개의 수의 합을 산정 //반복문을 통해 Math.sqrt(3개의 수의 합)까지 나누면서 계산 //계산할 때 1외의 값이 나온다면 소수가 아님을 판별 let sum = 0; let sumArr = []; for (let i = 0; i < nums.length - 2; i++) { for (let j = i + 1; j < nums.length; j++) { for (let k = j + 1; k < nums.length; k++) { sum = nums[i] + nums[j] + nums[k]; sumArr.push(sum); } } } sumArr.filter((num) => { let isPrime = true; for (let i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) { isPrime = false; break; } } if (isPrime) count++; }); return count; }
문제를 접근하는 방식은 다음과 같았다.
- 먼저 조합의 원리를 통해 배열에서 3개의 수를 뽑아 만드는 경우의 수를 새로운 배열에다 넣자.
- count 변수를 통해 numArr라는 배열에서 소수의 수를 세도록하자.
문제를 풀 때는 위와 같이 접근하려했다. 문제는 소수임을 판별하는 것과 조합을 어떤 식으로 구성할지였다.
for문을 사용해서 일일히 하자니 시간초과가 뜰 것 같고, 심지어 조합해서 똑같은 수가 나오는 경우도 생각해야하니 조건을 따질 것이 너무나 많았다.
let sum = 0; let sumArr = []; for (let i = 0; i < nums.length - 2; i++) { for (let j = i + 1; j < nums.length; j++) { for (let k = j + 1; k < nums.length; k++) { sum = nums[i] + nums[j] + nums[k]; sumArr.push(sum); } } }
우선 조합을 통해 숫자들의 합을 담아보자. sum은 3개의 숫자의 합, sumArr는 숫자를 담을 배열이다. 3중 for문을 이용하여 조합을 이용하는 방법이 있어서 위와 같이 했는데, 정말 읽기힘들다. 3개의 숫자를 뽑아야하므로 첫번째 변수 i는 nums.length-2까지의 수를 선택할 수 있다. 그 다음은 j,k는 이전에 선택한 값들보다 1만큼 큰 인덱스에서 숫자를 사용해야하므로 위와 같이 선택하도록했다.
이후 3개의 숫자를 sum에 넣고 push해서 배열에 넣어주었다.
sumArr.filter((num) => { let isPrime = true; for (let i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) { isPrime = false; break; } } if (isPrime) count++; }); return count; }
이제 다시 sumArr를 가지고 메서드를 활용하기로 했다. 소수 판별임을 확인하는 로직은 1과 자기자신 밖에 없어야하므로 isPrime이라는 변수를 true라 할당한 뒤 Math.sqrt(num), 즉 제곱근까지의 숫자로 수를 나눌때 한 번이라도 0이 되면 소수가 아니므로, 해당 케이스를 제외한 뒤, count를 증가시켰다.
문제점
먼저 중복되는 값이 발생할 수 있고, 코드 가독성 같은 부분도 있다. 아래는 모든 수단을 동원해서 더 나은 방법이 있는지 확인해본 거다.
sumArr = [...new Set(sumArr)];
중복을 제거한다. Set 메서드의 값은 1번만 나타나므로 스프레드 연산자로 한 번 나열하면 손쉽게 중복된 값을 제거한다.
에라토스테네스의 체
function generatePrimes(limit) { const isPrime = Array(limit + 1).fill(true); isPrime[0] = isPrime[1] = false; for (let i = 2; i <= Math.sqrt(limit); i++) { if (isPrime[i]) { for (let j = i * i; j <= limit; j += i) { isPrime[j] = false; } } } return isPrime; }
중학생땐가 한 번 들어본 것 같다. 수를 나열하고, 소수의 배수를 제거하며 소수임을 판단하는 것이다. 소수의 배수는 결국 소수가 아니기 때문이다.
const isPrime = Array(limit + 1).fill(true); isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님
배열을 생성하여 isPrime이라는 변수에 할당하였다.
for (let i = 2; i <= Math.sqrt(limit); i++) { if (isPrime[i]) { // 현재 숫자가 소수라면 for (let j = i * i; j <= limit; j += i) { // i의 배수를 모두 제거 isPrime[j] = false; // 소수가 아님 표시 } } }
위의 코드에서는 현재 숫자가 소수라면 해당 수의 배수는 모두 소수가 아님을 판단하고 모두 제거한다.
위와 같은 원리로 숫자들의 합을 담은 배열이 있다면 손쉽게 소수를 판별할 수 있다.
'프로그래머스' 카테고리의 다른 글
카드 뭉치 (0) 2025.03.07 최솟값 만들기 (그리디 알고리즘) (0) 2025.02.25 이상한 문자 만들기 (0) 2025.02.10 프로그래머스 - 과일 장수 (0) 2025.02.07 프로그래머스-문자열 내 마음대로 정렬하기 (1) 2025.01.02 다음글이전글이전 글이 없습니다.댓글