๐Ÿ’ก

319. Bulb Switcher - Medium

D A S H B O A R D
D E V E L O P
S E C U R I T Y

ย ๋ฌธ์ œ - 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}ย round, you toggle everyย iย bulb. For theย nthn^{th}ย 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 , 1
2.
2๋ฒˆ์งธ ๋ผ์šด๋“œ 1 , 0 , 1 , 0 , 1
3.
3๋ฒˆ์งธ ๋ผ์šด๋“œ 1 , 0 , 0 , 0 , 1
4.
4๋ฒˆ์งธ ๋ผ์šด๋“œ 1 , 0 , 0 , 1 , 1
5.
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}๋ฒˆ์งธ ์ „๊ตฌ์˜ ๊ฒฝ์šฐ ์ž์‹ ์˜ ์•ฝ์ˆ˜์ผ ๊ฒฝ์šฐ์— ์ „๊ตฌ๊ฐ€ ํ† ๊ธ€๋˜๊ฒŒ ๋˜๋Š” ๋ชจ์Šต์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.
โ€ข
๊ทธ๋ฆฌ๊ณ  ์•ฝ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ง์ˆ˜์ผ ๊ฒฝ์šฐ์—๋Š” OFF, ํ™€์ˆ˜์ผ ๊ฒฝ์šฐ์—๋Š” ON ์ด ๋˜๋Š” ๊ฒƒ๋„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.
โ€ข
์—ฌ๊ธฐ์„œ ์ƒ๊ฐ์น˜๋„ ๋ชปํ–ˆ๋Š”๋ฐ, ์•ฝ์ˆ˜๊ฐ€ ํ™€์ˆ˜๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ๋Š” ์ œ๊ณฑ๊ทผ ๋ฐ–์— ์—†๋‹คโ€ฆโ€ฆ.
โ—ฆ
์˜ˆ) 4\sqrt{4} โ‡’ 1 , 2 , 4 9\sqrt{9} โ‡’ 1 , 3 , 9 16\sqrt{16} โ‡’ 1 , 4 , 16
โ€ข
๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์— sqrt ํ•œ์ค„๋กœ ์ฝ”๋“œ๊ฐ€ ์™„์„ฑ๋˜๋Š” ๋ชจ์Šต์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.
n์ด ์™„์ „ ์ œ๊ณฑ์ผ ๋•Œ ์ „๊ตฌ๊ฐ€ ON ๋˜๋Š”๊ฑด ์•Œ๊ฒ ์–ด์š”! ๊ทธ๋Ÿผ 1~N๊นŒ์ง€ ์™„์ „ ์ œ๊ณฑ์ด ๋ช‡๊ฐœ ์žˆ๋Š”์ง€๋Š” ๋Œ€์ฒด ์–ด๋–ป๊ฒŒ ์•„์‹ ๊ฑด๊ฐ€์š”?
โ€ข
n = 25๋ผ๊ณ  ๊ฐ€์ •ํ•˜์ž!
โ—ฆ
๊ทธ๋ ‡๋‹ค๋ฉด n์€ 5์˜ ์™„์ „์ œ๊ณฑ์ด ๋œ๋‹ค. ์ด ๋•Œ 1~25์ค‘์— 1~5๊นŒ์ง€์˜ ์™„์ „์ œ๊ณฑ์ด ๋‹ค ํฌํ•จ๋œ๋‹ค. ์™œ๋ƒํ•˜๋ฉด 1~4๊นŒ์ง€์˜ ์™„์ „์ œ๊ณฑ ์ˆ˜๋Š” 25๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์—.