문제 설명
숫자 n이 주어지고, 방 안에는 n개의 스위치가 있다고 가정해 보겠습니다. 처음에 모든 스위치는 꺼져 있는 상태입니다. 이제 n명의 사람이 다음 규칙에 따라 차례로 스위치를 조작합니다.
- 1번 사람: 1의 배수에 해당하는 모든 스위치(즉, 전체 스위치)를 조작합니다.
- 2번 사람: 2의 배수(2, 4, 6, ...)에 해당하는 스위치를 조작합니다.
- i번 사람: i의 배수에 해당하는 스위치를 조작합니다.
목표는 모든 사람이 조작을 마친 후 최종적으로 켜져 있는 스위치의 개수를 구하는 것입니다.
예시
입력이 n = 5라면 출력은 2가 됩니다. 단계별 과정을 살펴보면 다음과 같습니다.
- 초기 상태: [0, 0, 0, 0, 0]
- 1번 사람 조작 후: [1, 1, 1, 1, 1] — 모든 스위치를 켭니다.
- 2번 사람 조작 후: [1, 0, 1, 0, 1] — 2번, 4번 스위치를 끕니다.
- 3번 사람 조작 후: [1, 0, 0, 0, 0] — 3번 스위치를 끕니다.
- 4번 사람 조작 후: [1, 0, 0, 1, 0] — 4번 스위치를 다시 켭니다.
- 5번 사람 조작 후: [1, 0, 0, 1, 0] — 5번 스위치를 끕니다.
최종적으로 켜져 있는 스위치는 1번과 4번, 총 2개입니다.
해결 접근 방법
이 문제의 핵심은 각 스위치가 조작되는 횟수에 있습니다. k번 스위치는 k의 약수 개수만큼 조작됩니다. 예를 들어 6번 스위치는 약수가 1, 2, 3, 6으로 네 개이므로 네 번 조작되어 결국 꺼진 상태로 돌아갑니다.
그런데 완전제곱수(1, 4, 9, 16, ...)만 약수의 개수가 홀수입니다. 완전제곱수가 아닌 수는 약수가 항상 쌍으로 존재하기 때문입니다. 따라서 최종적으로 켜져 있는 스위치의 개수는 n 이하의 완전제곱수의 개수, 즉 √n의 정수 부분(floor(√n))과 같습니다.
여기서는 이진 탐색(binary search)을 이용해 n의 정수 제곱근을 효율적으로 구하는 방식으로 문제를 해결합니다. 단계는 다음과 같습니다.
- l := 0, r := n으로 초기화합니다.
- l <= r인 동안 반복합니다.
- mid := l + (r - l) / 2를 계산합니다.
- mid² <= n < (mid + 1)²이면 mid가 정답이므로 mid를 반환합니다.
- n < mid²이면 r := mid로 갱신합니다.
- 그 외의 경우 l := mid + 1로 갱신합니다.
파이썬 구현 코드
class Solution: def solve(self, n): l, r = 0, n while l <= r: mid = l + (r - l) // 2 if mid * mid <= n < (mid + 1) * (mid + 1): return mid elif n < mid * mid: r = mid else: l = mid + 1 ob = Solution() n = 5 print(ob.solve(n))
입력
5
출력
2
복잡도 분석
이진 탐색을 사용하므로 시간 복잡도는 O(log n)이며, 별도의 저장 공간이 필요 없어 공간 복잡도는 O(1)입니다. 참고로 파이썬 3.8 이상에서는 math.isqrt(n) 함수를 사용하면 한 줄로 동일한 결과를 얻을 수 있습니다.