๋ฌธ์ ์ค๋ช
N๊ฐ์ ์ํํธ๊ฐ ์ผ๋ ฌ๋ก ์ญ ๋์ด์ ์์ต๋๋ค. ์ด ์ค์์ ์ผ๋ถ ์ํํธ ์ฅ์์๋ 4g ๊ธฐ์ง๊ตญ์ด ์ค์น๋์ด ์์ต๋๋ค. ๊ธฐ์ ์ด ๋ฐ์ ํด 5g ์์๊ฐ ๋์์ ธ 4g ๊ธฐ์ง๊ตญ์ 5g ๊ธฐ์ง๊ตญ์ผ๋ก ๋ฐ๊พธ๋ ค ํฉ๋๋ค. ๊ทธ๋ฐ๋ฐ 5g ๊ธฐ์ง๊ตญ์ 4g ๊ธฐ์ง๊ตญ๋ณด๋ค ์ ๋ฌ ๋ฒ์๊ฐ ์ข์, 4g ๊ธฐ์ง๊ตญ์ 5g ๊ธฐ์ง๊ตญ์ผ๋ก ๋ฐ๊พธ๋ฉด ์ด๋ค ์ํํธ์๋ ์ ํ๊ฐ ๋๋ฌํ์ง ์์ต๋๋ค.
์๋ฅผ ๋ค์ด 11๊ฐ์ ์ํํธ๊ฐ ์ญ ๋์ด์ ์๊ณ , [4, 11] ๋ฒ์งธ ์ํํธ ์ฅ์์๋ 4g ๊ธฐ์ง๊ตญ์ด ์ค์น๋์ด ์์ต๋๋ค. ๋ง์ฝ ์ด 4g ๊ธฐ์ง๊ตญ์ด ์ ํ ๋๋ฌ ๊ฑฐ๋ฆฌ๊ฐ 1์ธ 5g ๊ธฐ์ง๊ตญ์ผ๋ก ๋ฐ๋ ๊ฒฝ์ฐ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค. (์ ํ์ ๋๋ฌ ๊ฑฐ๋ฆฌ๊ฐ W์ผ ๋, ๊ธฐ์ง๊ตญ์ด ์ค์น๋ ์ํํธ๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ํ๋ฅผ ์์ชฝ์ผ๋ก W๋งํผ ์ ๋ฌํ ์ ์์ต๋๋ค.)
- ์ด๊ธฐ์, 1, 2, 6, 7, 8, 9๋ฒ์งธ ์ํํธ์๋ ์ ํ๊ฐ ์ ๋ฌ๋์ง ์์ต๋๋ค.
- 1, 7, 9๋ฒ์งธ ์ํํธ ์ฅ์์ ๊ธฐ์ง๊ตญ์ ์ค์นํ ๊ฒฝ์ฐ, ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค.
- ๋ ๋ง์ ์ํํธ ์ฅ์์ ๊ธฐ์ง๊ตญ์ ์ค์นํ๋ฉด ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค.
์ด๋, ์ฐ๋ฆฌ๋ 5g ๊ธฐ์ง๊ตญ์ ์ต์๋ก ์ค์นํ๋ฉด์ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ๋ ค๊ณ ํฉ๋๋ค. ์์ ์์์์ ์ต์ 3๊ฐ์ ์ํํธ ์ฅ์์ ๊ธฐ์ง๊ตญ์ ์ค์นํด์ผ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค.
์ํํธ์ ๊ฐ์ N, ํ์ฌ ๊ธฐ์ง๊ตญ์ด ์ค์น๋ ์ํํธ์ ๋ฒํธ๊ฐ ๋ด๊ธด 1์ฐจ์ ๋ฐฐ์ด stations, ์ ํ์ ๋๋ฌ ๊ฑฐ๋ฆฌ W๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ๊ธฐ ์ํด ์ฆ์คํด์ผ ํ ๊ธฐ์ง๊ตญ ๊ฐ์์ ์ต์๊ฐ์ ๋ฆฌํดํ๋ solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์
์ ํ ์ฌํญ
- N: 200,000,000 ์ดํ์ ์์ฐ์
- stations์ ํฌ๊ธฐ: 10,000 ์ดํ์ ์์ฐ์
- stations๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์๊ณ , ๋ฐฐ์ด์ ๋ด๊ธด ์๋ N๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์ ์์ฐ์์ ๋๋ค.
- W: 10,000 ์ดํ์ ์์ฐ์
์ ์ถ๋ ฅ ์
N | stations | W | answer |
11 | [4, 11] | 1 | 3 |
16 | [9] | 2 | 3 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ฌธ์ ์ ์์์ ๊ฐ์ต๋๋ค
์ ์ถ๋ ฅ ์ #2
- ์ด๊ธฐ์, 1~6, 12~16๋ฒ์งธ ์ํํธ์๋ ์ ํ๊ฐ ์ ๋ฌ๋์ง ์์ต๋๋ค.
- 3, 6, 14๋ฒ์งธ ์ํํธ ์ฅ์์ ๊ธฐ์ง๊ตญ์ ์ค์นํ ๊ฒฝ์ฐ ๋ชจ๋ ์ํํธ์ ์ ํ๋ฅผ ์ ๋ฌํ ์ ์์ต๋๋ค.
ํ์ด
- ์ด๋ป๊ฒ ํ๊น?
- ์ํํธ ๊ฐฏ์ N์ด ์๊ณ , 1๋ถํฐ N๊น์ง ๋ฐฐ์ด๋ก ๋ง๋ค๊ณ
- stations์ ํ์ฌ ์ํ ๋ ์์น๊ณ , W๊ฐ ์ํ ๋์ ๋ฒ์
- ๊ทธ๋ผ 1์ฐจ์ ๋ฐฐ์ด ํ๋ ๋ ๋ง๋ค์ด์ ์์น ํ๋ฉด์ ํ๋ฉด ๋๋ ค๋?
- ๋น์นธ ์์น ๊ฐ๊ฒฉ์ 2*W+1, ์ํ ๋ ์์น๋ ์ค์ํ์ง ์๊ตฐ. ์ค์น ์ง์ ์ด ์๋๋ผ ๋ฒ์๋๊น
- ์ด์ฐ.. ์๋๋ค.
- N์ด 200000000 ์ดํ ์์ฐ์๋ค. ๋ฐฐ์ด๋ก ์ฒดํฌํ๋ฉด ํฐ์ง๋ค. ใ ใ ใ
- ๊ฒ๋ค๊ฐ ํจ์จ์ฑ ํ ์คํธ๋ ์๋ค?
- ๊ทธ๋ฅ ์ซ์๋ก ํ์ด์ผ ๋๋ค, ์ผ๋จ stations๋ฅผ ์ํ
ํ๊ณ ...
- ์ด๊ฑฐ ์์ฒญ ์ฐ์ด๋ด์ผํ๋ค. ใ
ใ
ใ
ใ
- print(์ค์น๊ธฐ์ฌ,์ํ ๋_๋ฒ์_์์,์ํ ๋_๋ฒ์_์ข ๋ฃ)
- ์ด๊ฑฐ ์์ฒญ ์ฐ์ด๋ด์ผํ๋ค. ใ
ใ
ใ
ใ
def solution(n, stations, w):
answer = 0
stations.sort()
www = 2*w+1
์ค์น๊ธฐ์ฌ = 1
for ์ํ
๋ in stations:
์ํ
๋_๋ฒ์_์์ = ์ํ
๋ - w
์ํ
๋_๋ฒ์_์ข
๋ฃ = ์ํ
๋ + w
if ์ค์น๊ธฐ์ฌ < ์ํ
๋_๋ฒ์_์์ or ์ํ
๋_๋ฒ์_์ข
๋ฃ < ์ค์น๊ธฐ์ฌ:
ํ์๊ฐฏ์ = (์ํ
๋_๋ฒ์_์์ - ์ค์น๊ธฐ์ฌ) // www
if (์ํ
๋_๋ฒ์_์์ - ์ค์น๊ธฐ์ฌ) % www != 0:
ํ์๊ฐฏ์ += 1
answer += ํ์๊ฐฏ์
์ค์น๊ธฐ์ฌ = ์ํ
๋_๋ฒ์_์ข
๋ฃ + 1
if ์ค์น๊ธฐ์ฌ <= n:
์ํ
๋_๋ฒ์_์์ = n + 1
ํ์๊ฐฏ์ = (์ํ
๋_๋ฒ์_์์ - ์ค์น๊ธฐ์ฌ) // www
if (์ํ
๋_๋ฒ์_์์ - ์ค์น๊ธฐ์ฌ) % www != 0:
ํ์๊ฐฏ์ += 1
answer += ํ์๊ฐฏ์
return answer
- ์ด์ฐ ํ์ด์ฌ ํ๊ธ ๋๋๊น ๋๋ฌด ์ข๋ค.
- ์์ ๊ฐ๊ฟ ใ
ใ
ใ
- ๋ฌด์ง์ฑ ์ฝ๋ฉ ํ๊ธฐ ์ข๋ค.
- ์์ ๊ฐ๊ฟ ใ
ใ
ใ
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.00ms, 10.4MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.00ms, 10.4MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.00ms, 10.6MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.00ms, 10.4MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.00ms, 10.5MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.00ms, 10.4MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.00ms, 10.6MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.00ms, 10.4MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 20 ใ ํต๊ณผ (0.00ms, 10.6MB)
ํ
์คํธ 21 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (1.64ms, 10.5MB)
ํ
์คํธ 2 ใ ํต๊ณผ (1.70ms, 10.6MB)
ํ
์คํธ 3 ใ ํต๊ณผ (1.57ms, 10.8MB)
ํ
์คํธ 4 ใ ํต๊ณผ (1.78ms, 10.6MB)
- ๊ณ ์์ ์ฝ๋...
- ์ฝ๋ ๊ธธ์ด ์งง์. ์ง๋ฆฌ์ง๋ง ์ํ ๋ ์ค์น ๊ฐ๊ฒฉ์ผ๋ก n๋งํผ ๋ฃจํ ๋๋ฆฌ๋ฉด ๋๋ฆฌ๋ค.
def solution(n, stations, w):
ans = 0
idx = 0
location = 1
while(location <= n) :
if(idx < len(stations) and location >= stations[idx]-w) :
location = stations[idx]+w+1
idx += 1
else :
location += 2*w+1
ans += 1
return ans
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.00ms, 10.4MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 20 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 21 ใ ํต๊ณผ (0.02ms, 10.3MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (3.08ms, 10.5MB)
ํ
์คํธ 2 ใ ํต๊ณผ (4.58ms, 10.6MB)
ํ
์คํธ 3 ใ ํต๊ณผ (4.30ms, 10.5MB)
ํ
์คํธ 4 ใ ํต๊ณผ (3.71ms, 10.6MB)
- ์ง์ง ๊ณ ์๋ค. ์ง๋ ธ๋ค.
def solution(n, arr, w):
bef=-w
cnt=0
ww=w*2+1
for x in arr:
cnt+=(x-bef-1)//ww
bef=x
return cnt+(n+w-bef)//ww
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 20 ใ ํต๊ณผ (0.00ms, 10.3MB)
ํ
์คํธ 21 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.90ms, 10.4MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.91ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.89ms, 10.4MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.90ms, 10.4MB)
'๊ฒ์ ํ๋ก๊ทธ๋๋ฐ > Python ํ๋ก๊ทธ๋๋ฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค ๋ฉ๋ด ๋ฆฌ๋ด์ผ 2021 KAKAO BLIND RECRUITMENT (1) | 2023.02.28 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค ๋ถ๋ ์ฌ์ฉ์ 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ (0) | 2023.02.28 |
ํ๋ก๊ทธ๋๋จธ์ค ์ซ์๊ฒ์ Summer/Winter Coding (~2018) (0) | 2023.02.28 |
ํ๋ก๊ทธ๋๋จธ์ค ๊ดํธ๋ณํ (2020 KAKAO BLIND RECRUITMENT) (0) | 2023.02.27 |
ํ๋ก๊ทธ๋๋จธ์ค ์ฌ ์ฐ๊ฒฐํ๊ธฐ (0) | 2023.02.27 |