JavaScript로 전구 켜고 끄기: n번의 라운드 후 켜진 전구 개수 구하기

문제 소개

다음과 같은 상황을 생각해 봅시다.

처음에는 모두 꺼져 있는 전구가 n개 있습니다. 첫 번째 라운드에서는 모든 전구를 켭니다. 두 번째 라운드에서는 두 번째마다 해당하는 전구를 끕니다. 세 번째 라운드에서는 세 번째마다 해당하는 전구의 상태를 반전시킵니다(꺼져 있으면 켜고, 켜져 있으면 끕니다).

일반화하면, i번째 라운드에서는 i번째마다 해당하는 전구의 상태를 반전시키며, 마지막 n번째 라운드에서는 마지막 전구 하나만 반전시킵니다.

즉, 숫자 n을 유일한 입력으로 받아 n번의 라운드가 모두 끝난 후 켜져 있는 전구가 몇 개인지 구하는 JavaScript 함수를 작성해야 합니다.

예시

함수의 입력이 다음과 같다고 하면,

const n = 5;

출력은 다음과 같아야 합니다.

const output = 2;

출력 설명

상태 배열에서 0은 꺼진 상태, 1은 켜진 상태를 의미합니다.

다섯 번째 라운드가 끝난 후에는 두 개의 전구만 켜져 있는 것을 확인할 수 있습니다.

핵심 아이디어: 완전제곱수

k번째 전구는 k의 약수에 해당하는 라운드마다 정확히 한 번씩 상태가 반전됩니다. 예를 들어 6번 전구는 약수가 1, 2, 3, 6으로 네 개이므로 네 번 반전되어 결국 꺼진 상태로 돌아갑니다. 반면 약수의 개수가 홀수인 수는 완전제곱수뿐입니다. 4의 약수는 1, 2, 4로 세 개이므로 세 번 반전된 후 켜진 상태로 남게 됩니다.

따라서 최종적으로 켜져 있는 전구의 개수는 n 이하의 완전제곱수의 개수, 즉 ⌊√n⌋과 같습니다. n = 5일 때 완전제곱수는 1과 4뿐이므로 정답은 2가 됩니다.

예제 코드

큰 수에서도 부동소수점 오차 없이 정수 제곱근을 정확히 구하기 위해 이진 탐색을 활용할 수 있습니다.

const n = 5;
const findOn = (n = 1) => {
    let off = 0;
    let on = n;
    while(off <= on){
        let mid = Math.floor((off + on) / 2);
        if(mid * mid > n){
            on = mid - 1;
        }else{
            off = mid + 1;
        };
    };
    return Math.floor(on);
};
console.log(findOn(n));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

2