알고리즘 이야기/알고리즘 문제풀이

JS 알고리즘 - parseInt, Math.sqrt(num), 소수(prime number) 개념 이해

thisisamrd 2023. 10. 8.

오늘은 아래와 같은 문제를 풀었다.

해당 문제를 풀면서 기본기가 어서 잡혀야겠다는 생각을 했다.

문제

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

▣ 입력설명  
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다.  
각 자연수의 크기는 100,000를 넘지 않는다.  
▣ 출력설명  
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.  
▣ 입력예제 1  
9  
32 55 62 20 250 370 200 30 100  
▣ 출력예제 1  
23 2 73 2 3

해답

위 문제에 대한 해답은 이러하다.

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            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=0; // res는 뒤집힌 숫자를 저장하기 위한 변수
                    while(x){ // 해당 while문이 한번 돌면서 앞뒤가 뒤바뀐 숫자를 출력함
                        console.log('res: ' + res)
                        let t=x%10; // x의 맨 오른쪽 숫자 (일의 자리) 
                        console.log('t: ' + t)
                        res=res*10+t; // res를 10배하고 t를 더하여 res에 저장한다. (이렇게 하면 숫자가 뒤집히게 됨.)
                        console.log('res2: ' + res)
                        x=parseInt(x/10); // x/10은 0.3, parseInt는 정수만 나오게 한다
                        console.log('x: ' + x)
                    }
                    if(isPrime(res)) answer.push(res);
                }
                return answer;
            }
            
            let arr=[32, 55, 62, 20, 250, 370, 200, 30, 100];
            console.log(solution(arr));
        </script>
    </body>
</html>

위 문제를 풀기 위한 개념 몇 가지를 정리해보았다.

개념 정리

1. 소수(Prime number)의 개념

"소수"는 어떤 수가 1과 자기 자신 외에는 어떤 자연수로도 나누어지지 않는 수를 의미한다.

다르게 표현하면, 약수가 1과 자기 자신뿐인 수를 소수라고 한다.

ex)
2는 소수이다. 2 외에는 2를 나눌 수 있는 수가 없다.
3도 소수이다. 1과 3만이 3의 약수이다.
4는 소수가 아니다. 1, 2, 4가 모두 4의 약수이다. (2 × 2 = 4)

2. Math.sqrt(num)에 대하여

Math.sqrt(num)은 JavaScript에서 제공하는 Math 객체의 sqrt 메서드를 사용한 것으로, 주어진 num의 제곱근(square root)을 반환한다.
제곱근은 어떤 수를 자기 자신으로 곱했을 때 원래의 수(num)가 되는 수를 의미한다.

ex)
Math.sqrt(4)는 2를 반환한다. 왜냐하면 2×2=4이기 때문이다.
Math.sqrt(9)는 3을 반환합니다. 왜냐하면 3×3=9이기 때문이다.
Math.sqrt(2)는 약 1.414를 반환합니다. 왜냐하면 1.414×1.414≈2이기 때문이다.

그런데 이 함수는 소수 판별 알고리즘에서 효율성을 높이기 위해 사용된다. 위 문제에 대한 해설에서도 마찬가지이다.

어떤 수 num이 소수가 아니라면, 그 수의 약수 중 하나는 반드시 num의 제곱근 이하에 존재하기 때문에 제곱근까지만 검사를 하면 효과적으로 소수를 판별할 수 있다.

3. parseInt

나누기를 이용해야 하는 문제에서 단골로 등장하는 자바스크립트 함수이다.

나는 그냥 몫을 구할 때 '/'를 사용 후 parseInt해주면 된다고 외워버렸는데 이 기회에 다시 개념을 정리해본다.

parseInt는 주어진 문자열을 정수로 변환한다. 그리고 만약 문자열이 숫자로 시작하지 않으면 NaN을 반환한다.

변환 중간에 숫자가 아닌 문자를 만나면, 그 문자에서 변환을 중단하고 그 이전까지의 숫자를 반환한다.

ex)

console.log(parseInt("123abc"));  // 출력: 123
console.log(parseInt("abc123"));  // 출력: NaN
console.log(parseInt("10.5"));    // 출력: 10

또한 parseInt는 두 번째 인수로 기수(radix)를 선택적으로 받아들인다. 기수는 변환될 문자열이 사용하는 숫자 체계를 나타내며, 2에서 36까지의 값을 가질 수 있다. 예를 들면, 10은 10진수를 의미하고, 2는 2진수를 의미한다.

ex)

console.log(parseInt("1101", 2));  // 2진수 "1101"을 10진수로 변환한 결과는 13이므로 출력: 13

저작자표시 비영리 변경금지

'알고리즘 이야기 > 알고리즘 문제풀이' 카테고리의 다른 글

JS 알고리즘 - DFS로 부분집합 구하기 (1)	2023.11.25
JS 알고리즘 - sort(), Math.max() (1)	2023.10.09
JS 알고리즘 - 2차원 탐색 상하좌우 (1)	2023.10.01
JS 알고리즘 - indexOf(), filter (0)	2023.09.30
JS 알고리즘 TIL - 가장 긴 문자열 (0)	2023.09.29