[프로그래머스 Lv.2] k진수에서 소수 개수 구하기 (자바스크립트)

레벨: 2

출처: 2022 KAKAO Blind Recruitment

링크: https://school.programmers.co.kr/learn/courses/30/lessons/92335

정답까지 내 소요시간: 37분. 아쉽다 ㅠ 첫 제출까지는 25분이었지만, 정확도 89점이었음.

 

🎮 나의 풀이

이번 문제의 핵심 구현 사항은 간단했다.

(1) 주어진 k진수로 n을 변형하는 것

(2) 변형된 n에서 요구 조건을 만족하는 소수를 카운트하는 것

1️⃣ 주어진 k진수로 n을 변형하는 것

놀라운 일이 있다. 이 글을 작성하면서 굳이 내가 했던 방식대로 k진수 변형을 하지 않았어도 됐다는 게 떠올랐다 😂

ㅎ 그치만 좋은 연습이었다!

 

진수 변환의 원리를 떠올렸을 때, 계속 k로 나눗셈을 하며 나온 나머지를 붙이는 과정이었기 때문에 그대로 구현하였다.

나눗셈을 지속하다가 몫이 k보다 작아졌을 때 나눗셈을 멈추도록 정의하였다.

let newNum = ''; // 진수전환
let answer = 0;
let share = n;

while(share >= k) {
    newNum = String(share % k) + newNum;
    share = Math.trunc(share / k);
}

newNum = String(share) + newNum; //맨 앞부분 삽입

 

마지막 몫이 맨 앞에 위치해야하기 때문에, 반복문 이후에 따로 붙여주었다. 

 

2️⃣ 변형된 n에서 요구 조건을 만족하는 소수를 카운트하는 것

> 일단 요구 조건에 맞는 소수는 0을 포함하지 않기 때문에, 변형된 n을 '0'을 기준으로 나누어 배열로 저장했다.

 

> 이후 하나씩 순회하면서 소수인지를 판단하고, 해당할 경우 카운트를 올려주었다. 여기까지는 매우 순조로웠다. 소수 판단은 1과 자신을 제외한 숫자 중 하나라도 나눠떨어지는 게 있으면 제외시키는 방식을 쓰면 되기 때문이다. 

 

🚨 두 개의 케이스에서 시간초과

처음에는 아래와 같이 forEach문을 활용해서 처리했다. 2개의 케이스에서 시간 초과가 나와서 89점의 정확도를 받고 실패...

newNum.split('0').forEach((word) => {
	num = Number(num);
	let flag = 0
	
	if(!isNaN(num) && num >1) {
		for (let i=2; i<num; i++) {
			if(num%i==0) {
				flag += 1;
			}
		}
		if (flag==0) {
			answer += 1;
		}
	}
})

 

🚨 한 개의 케이스에서 시간초과

시간을 줄이기 위해서 진수 변환은 필수적이니, 소수 판단 과정에서 시간을 줄여야된다고 생각했다. 소수는 1,자기자신 제외 하나라도 약수가 있으면 아니기 때문에 모든 반복을 돌지 않도록 break를 추가하면 나아질 것이라 생각하여 수정했다.

 

그랬더니 1개의 케이스에서 시간초과가 나는 것으로 줄었다 ㅋㅋ..

for (let num of newNum.split('0')) {
    num = Number(num);
    let flag = 0;

    if(!isNaN(num) && num>1) {
        for (let i=2; i<num); i++) {
            if(num % i == 0) {
                flag += 1;
                break;
            }
        }

        if(flag==0) {
            console.log(num)
            answer += 1;
        }
    }
}

 

🚨 드디어 통과 .. ^^

소수를 판단하는 다양한 방법을 찾기로 했다. 인터넷에서 제곱근까지만 검사하는 것이 가장 효율적으로 판단되어 해당 방식으로 수정하고 드디어 성공!

for (let num of newNum.split('0')) {
        num = Number(num);
        let flag = 0;
        
        if(!isNaN(num) && num>1) {
            for (let i=2; i<=parseInt(Math.sqrt(num)); i++) {
                if(num % i == 0) {
                    flag += 1;
                    break;
                }
            }
            
            if(flag==0) {
                console.log(num)
                answer += 1;
            }
        }
    }

 

📩 레슨런

> A라는 숫자가 소수인지 판단할 때, 기본적으로 2부터 A-1까지 순회하기 때문에 시간복잡도는 O(n)이다.

 

> 만약 (1과 자기 자신을 제외한) 약수가 있다면, 그 약수는 A의 절반보다 클 수 없다.

따라서, 2부터 A의 절반까지만 순회하여 반복을 줄일 수 있지만 여전히 O(n)의 시간복잡도를 갖는다.

 

> 그런데 약수는 어차피 짝을 이룬다. 

16의 약수는 1, 2, 4, 8, 16인데 (1,16) - (2,8) - (4)로 짝을 이룬다. 

10의 약수는 1, 2, 5, 10인데 (1,10) - (2,5)로 짝을 이룬다.

 

해당 짝들의 중간 점에 있는 제곱근까지 검사했을 때 약수가 없다면, 제곱근 이후 나머지 숫자들 중에도 약수가 없다는 것이다.

따라서, 2부터 A의 제곱근까지만 순회하도록 반복을 줄이면 O(n제곱근)의 시간복잡도로 더 효율적이다.

 

🧐 좋은 풀이 톺아보기

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

function solution(n, k) {    
    // k진법으로 나눈 후 split
    const candidates = n.toString(k).split('0');
    // 소수 개수 세기
    return candidates.filter(v=>isPrime(+v)).length;
}

 

전체적인 처리는 대부분 나와 비슷하다. 그런데, 아래의 부분들이 다르다.

- 소수 판별 부분을 함수로 분리하여 처리한 것

- 소수가 아닐 경우만 간단하게 false로 리턴하여 판단한 것 (내가 flag를 쓴 것보다 더 심플한 방식)

- filter함수를 활용하여 카운트 한 것

 

가독성 측면에서 훨씬 깔끔한 것 같다. 특히 소수 판단하는 부분이 더 심플한 게 배울 점인 것 같다.