문제 소개
학교 축제 행사에서 다음과 같은 게임을 진행한다고 가정해 보겠습니다.
n개의 수도꼭지가 준비되어 있고, n명의 학생이 무작위로 선발됩니다. 지도 교사는 첫 번째 학생에게 모든 수도꼭지를 열어 보라고 지시합니다. 이어서 두 번째 학생은 2번째마다 해당하는 수도꼭지를 찾아가 잠그고, 세 번째 학생은 3번째마다 해당하는 수도꼭지가 닫혀 있으면 열고 열려 있으면 닫습니다. 네 번째 학생은 4번째마다 같은 작업을 수행하며, 이 과정이 n번째 학생까지 계속됩니다.
모든 과정이 끝난 후, 몇 개의 수도꼭지가 열려 있을까요? 우리는 숫자 n을 입력받아 열려 있는 수도꼭지의 개수를 반환하는 JavaScript 함수를 작성해야 합니다.
접근 방식: 완전제곱수의 비밀
k번째 수도꼭지는 자신의 번호 k의 약수에 해당하는 학생들에 의해 켜졌다 꺼집니다. 예를 들어 6번 수도꼭지는 1, 2, 3, 6번 학생이 각각 조작하므로 최종적으로 닫힌 상태가 됩니다.
약수는 대부분 (1, k), (a, b)처럼 쌍으로 존재하기 때문에 조작 횟수가 짝수가 되어 결국 닫히게 됩니다. 하지만 완전제곱수만은 √k × √k = k처럼 약수가 중복되어 홀수 개의 약수를 가지며, 마지막에 열린 상태로 남게 됩니다.
따라서 정답은 n 이하의 완전제곱수의 개수, 즉 ⌊√n⌋입니다. 이 원리를 활용하면 전체 시뮬레이션 없이도 매우 효율적으로 답을 구할 수 있습니다.
예제 코드
const num = 15;
const openTaps = (num = 1) => {
const arr = [];
let index = 1;
while(index ** 2 <= num){
arr.push(index++ ** 2);
};
return arr.length;
};
console.log(openTaps(num));출력 결과
7
코드 설명
함수 내부에서는 index를 1부터 시작하여 index의 제곱이 num 이하일 동안 반복하면서 각 완전제곱수(1, 4, 9, ...)를 배열에 저장합니다. num이 15일 때 완전제곱수는 1, 4, 9로 3개... 가 아니라 1, 4, 9, ... 중 15 이하인 값들을 모두 세면 됩니다. 실제로 1, 4, 9, 16 중 16은 15를 초과하므로, 위 코드에서는 index ** 2 <= num 조건에 맞는 값들이 배열에 쌓이고, 그 배열의 길이가 곧 열려 있는 수도꼭지의 개수가 됩니다.
이 방법은 시간 복잡도가 O(√n)으로, n이 커져도 빠르게 동작합니다. 단순히 Math.floor(Math.sqrt(num))을 반환하는 한 줄로도 동일한 결과를 얻을 수 있습니다.