💡

319. Bulb Switcher - Medium

D A S H B O A R D

Hyeon-Stone

D E V E L O P

S E C U R I T Y

Bulb Switcher - LeetCode

Can you solve this real interview question? Bulb Switcher - There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Return the number of bulbs that are on after n rounds. Example 1: [https://assets.leetcode.com/uploads/2020/11/05/bulb.jpg] Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on. Example 2: Input: n = 0 Output: 0 Example 3: Input: n = 1 Output: 1 Constraints: * 0 <= n <= 109

https://leetcode.com/problems/bulb-switcher/

문제 - 319. Bulb Switcher

•

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

•

On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ithi^{th}ith round, you toggle every i bulb. For the nthn^{th}nth round, you only toggle the last bulb.

•

Return the number of bulbs that are on after n rounds.

해석

•

n개의 전구가 있다.

•

첫번째 라운드에서는 모든 전구를 킨다.

•

두번째 라운드에서는 모든 2의 배수의 전구를 끈다.

•

3번째 라운드 부터는 i번째 라운드마다 i의 모든 배수의 전구를 토글한다.

•

마지막 n번째 라운드에서는 오직 마지막 전구만을 토글한다.

•

라운드는 총 n번 돌고, 마지막에 켜져 있는 전구의 수를 return 하라

첫 코드 : 9999999 TestCase에서 시간 초과

class Solution:
    def bulbSwitch(self, n: int) -> int:
        if n == 1:
            return 1
        bulbs = [True for _ in range(n)]
        for i in range(1, n//2):
            for j in range(i, n-n%(i+1), i+1):
                bulbs[j] ^= True
        for i in range(n//2, n):
            bulbs[i] ^= True
        return bulbs.count(1)
Python
복사

•

위 로직은 n이 2 이상일 경우를 생각해서 구현하였기 때문에 n이 1일 경우에는 바로 return

•

for문 2개는 i의 배수인 모든 전구를 토글해주어야 하는데, 이 때 n개라는 전구 안에서 배수가 있으려면 n//2 보다 i가 작아야 배수가 존재하기 때문에 두개의 for문으로 구성

◦

예) n= 4 일 때 배수가 존재하는 수는 1, 2

◦

예) n= 5 일 때 배수가 존재하는 수도 1, 2

◦

예) n = 6 일 때 배수가 존재하는 수는 1, 2, 3

•

하지만 해당 코드는 시간초과로 통과하지 못함

Discuss를 보고 푼 코드

import math
class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(math.sqrt(n))
Python
복사

•

세상에 수학적 재능을 타고난 인간이 많다고 새삼 느껴진다……..

•

딱 1줄의 코드로 완성이 된다.

설명

n = 5라고 가정해보자

1번째  라운드  1 , 1 , 1 , 1 , 1

2번째 라운드   1 , 0 , 1 , 0 , 1

3번째 라운드   1 , 0 , 0 , 0 , 1

4번째 라운드   1 , 0 , 0 , 1 , 1

5번째 라운드   1 , 0 , 0 , 1 , 0

이제 인덱스 별로 살펴보자

•

0번 인덱스(1번째 전구)가 바뀌는 경우 : i == 1 

•

1번 인덱스(2번째 전구)가 바뀌는 경우 : i == 1 , i == 2

•

2번 인덱스(3번째 전구)가 바뀌는 경우 : i == 1 , i == 3

•

3번 인덱스(4번째 전구)가 바뀌는 경우 : i == 1 , i == 2, i == 4

•

4번 인덱스(5번째 전구)가 바뀌는 경우 : i == 1 , i == 5

이제 규칙을 살펴보자

•

nthn^{th}nth번째 전구의 경우 자신의 약수일 경우에 전구가 토글되게 되는 모습을 볼 수 있다.

•

그리고 약수의 개수가 짝수일 경우에는 OFF, 홀수일 경우에는 ON 이 되는 것도 알 수 있다.

•

여기서 생각치도 못했는데, 약수가 홀수가 되는 경우는 제곱근 밖에 없다…….

◦

예) 
4\sqrt{4}4​ ⇒ 1 , 2 , 4
9\sqrt{9}9​ ⇒ 1 , 3 , 9
16\sqrt{16}16​ ⇒ 1 , 4 , 16

•

그렇기 때문에 sqrt 한줄로 코드가 완성되는 모습을 볼 수 있다.

n이 완전 제곱일 때 전구가 ON 되는건 알겠어요! 그럼 1~N까지 완전 제곱이 몇개 있는지는 대체 어떻게 아신건가요?

•

n = 25라고 가정하자!

◦

그렇다면 n은 5의 완전제곱이 된다. 
이 때 1~25중에 1~5까지의 완전제곱이 다 포함된다. 왜냐하면 1~4까지의 완전제곱 수는 25보다 작기 때문에.