๋ฌธ์ ์ค๋ช
์ด๋ ํ๊ต์ ํ์ธํธ๊ฐ ์น ํด์ง ๊ธธ์ด๊ฐ n๋ฏธํฐ์ธ ๋ฒฝ์ด ์์ต๋๋ค. ๋ฒฝ์ ๋์๋ฆฌ · ํํ ํ๋ณด๋ ํ์ฌ ์ฑ์ฉ ๊ณต๊ณ ํฌ์คํฐ ๋ฑ์ ๊ฒ์ํ๊ธฐ ์ํด ํ ์ดํ๋ก ๋ถ์๋ค๊ฐ ์ฒ ๊ฑฐํ ๋ ๋ผ๋ ์ผ์ด ๋ง๊ณ ๊ทธ ๊ณผ์ ์์ ํ์ธํธ๊ฐ ๋ฒ๊ฒจ์ง๊ณค ํฉ๋๋ค. ํ์ธํธ๊ฐ ๋ฒ๊ฒจ์ง ๋ฒฝ์ด ๋ณด๊ธฐ ํํด์ ธ ํ๊ต๋ ๋ฒฝ์ ํ์ธํธ๋ฅผ ๋ง์น ํ๊ธฐ๋ก ํ์ต๋๋ค.
๋์ ๋ฒฝ ์ ์ฒด์ ํ์ธํธ๋ฅผ ์๋ก ์น ํ๋ ๋์ , ๊ตฌ์ญ์ ๋๋์ด ์ผ๋ถ๋ง ํ์ธํธ๋ฅผ ์๋ก ์น ํจ์ผ๋ก์จ ์์ฐ์ ์๋ผ๋ ค ํฉ๋๋ค. ์ด๋ฅผ ์ํด ๋ฒฝ์ 1๋ฏธํฐ ๊ธธ์ด์ ๊ตฌ์ญ n๊ฐ๋ก ๋๋๊ณ , ๊ฐ ๊ตฌ์ญ์ ์ผ์ชฝ๋ถํฐ ์์๋๋ก 1๋ฒ๋ถํฐ n๋ฒ๊น์ง ๋ฒํธ๋ฅผ ๋ถ์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ํ์ธํธ๋ฅผ ๋ค์ ์น ํด์ผ ํ ๊ตฌ์ญ๋ค์ ์ ํ์ต๋๋ค.
๋ฒฝ์ ํ์ธํธ๋ฅผ ์น ํ๋ ๋กค๋ฌ์ ๊ธธ์ด๋ m๋ฏธํฐ์ด๊ณ , ๋กค๋ฌ๋ก ๋ฒฝ์ ํ์ธํธ๋ฅผ ํ ๋ฒ ์น ํ๋ ๊ท์น์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ๋กค๋ฌ๊ฐ ๋ฒฝ์์ ๋ฒ์ด๋๋ฉด ์ ๋ฉ๋๋ค.
- ๊ตฌ์ญ์ ์ผ๋ถ๋ถ๋ง ํฌํจ๋๋๋ก ์น ํ๋ฉด ์ ๋ฉ๋๋ค.
์ฆ, ๋กค๋ฌ์ ์ข์ฐ์ธก ๋์ ๊ตฌ์ญ์ ๊ฒฝ๊ณ์ ํน์ ๋ฒฝ์ ์ข์ฐ์ธก ๋๋ถ๋ถ์ ๋ง์ถ ํ ๋กค๋ฌ๋ฅผ ์์๋๋ก ์์ง์ด๋ฉด์ ๋ฒฝ์ ์น ํฉ๋๋ค. ํ์ฌ ํ์ธํธ๋ฅผ ์น ํ๋ ๊ตฌ์ญ๋ค์ ์์ ํ ์น ํ ํ ๋ฒฝ์์ ๋กค๋ฌ๋ฅผ ๋ผ๋ฉฐ, ์ด๋ฅผ ๋ฒฝ์ ํ ๋ฒ ์น ํ๋ค๊ณ ์ ์ํฉ๋๋ค.
ํ ๊ตฌ์ญ์ ํ์ธํธ๋ฅผ ์ฌ๋ฌ ๋ฒ ์น ํด๋ ๋๊ณ ๋ค์ ์น ํด์ผ ํ ๊ตฌ์ญ์ด ์๋ ๊ณณ์ ํ์ธํธ๋ฅผ ์น ํด๋ ๋์ง๋ง ๋ค์ ์น ํ๊ธฐ๋ก ์ ํ ๊ตฌ์ญ์ ์ ์ด๋ ํ ๋ฒ ํ์ธํธ์น ์ ํด์ผ ํฉ๋๋ค. ์์ฐ์ ์๋ผ๊ธฐ ์ํด ๋ค์ ์น ํ ๊ตฌ์ญ์ ์ ํ๋ฏ ๋ง์ฐฌ๊ฐ์ง๋ก ๋กค๋ฌ๋ก ํ์ธํธ์น ์ ํ๋ ํ์๋ฅผ ์ต์ํํ๋ ค๊ณ ํฉ๋๋ค.
์ ์ n, m๊ณผ ๋ค์ ํ์ธํธ๋ฅผ ์น ํ๊ธฐ๋ก ์ ํ ๊ตฌ์ญ๋ค์ ๋ฒํธ๊ฐ ๋ด๊ธด ์ ์ ๋ฐฐ์ด section์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋ ๋กค๋ฌ๋ก ํ์ธํธ์น ํด์ผ ํ๋ ์ต์ ํ์๋ฅผ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
์ ํ ์ฌํญ
- 1 ≤ m ≤ n ≤ 100,000
- 1 ≤ section์ ๊ธธ์ด ≤ n
- 1 ≤ section์ ์์ ≤ n
- section์ ์์๋ ํ์ธํธ๋ฅผ ๋ค์ ์น ํด์ผ ํ๋ ๊ตฌ์ญ์ ๋ฒํธ์ ๋๋ค.
- section์์ ๊ฐ์ ์์๊ฐ ๋ ๋ฒ ์ด์ ๋ํ๋์ง ์์ต๋๋ค.
- section์ ์์๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
n | m | section | result |
8 | 4 | [2, 3, 6] | 2 |
5 | 4 | [1, 3] | 1 |
4 | 1 | [1, 2, 3, 4] | 4 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์ ์ถ๋ ฅ ์ #1
- ์์ 1๋ฒ์ 2, 3, 6๋ฒ ์์ญ์ ํ์ธํธ๋ฅผ ๋ค์ ์น ํด์ผ ํฉ๋๋ค. ๋กค๋ฌ์ ๊ธธ์ด๊ฐ 4๋ฏธํฐ์ด๋ฏ๋ก ํ ๋ฒ์ ํ์ธํธ์น ์ ์ฐ์๋ 4๊ฐ์ ๊ตฌ์ญ์ ์น ํ ์ ์์ต๋๋ค. ์ฒ์์ 3, 4, 5, 6๋ฒ ์์ญ์ ํ์ธํธ์น ์ ํ๋ฉด ์น ํด์ผ ํ ๊ณณ์ผ๋ก 2๋ฒ ๊ตฌ์ญ๋ง ๋จ๊ณ 1, 2, 3, 4๋ฒ ๊ตฌ์ญ์ ํ์ธํธ์น ์ ํ๋ฉด 2๋ฒ ๋ง์ ๋ค์ ์น ํด์ผ ํ ๊ณณ์ ๋ชจ๋ ํ์ธํธ์น ์ ํ ์ ์์ต๋๋ค.2๋ฒ๋ณด๋ค ์ ์ ํ์๋ก 2, 3, 6๋ฒ ์์ญ์ ํ์ธํธ๋ฅผ ๋ง์น ํ๋ ๋ฐฉ๋ฒ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ต์ ํ์์ธ 2๋ฅผ return ํฉ๋๋ค.
์ ์ถ๋ ฅ ์ #2
- ์์ 2๋ฒ์ 1, 3๋ฒ ์์ญ์ ํ์ธํธ๋ฅผ ๋ค์ ์น ํด์ผ ํฉ๋๋ค. ๋กค๋ฌ์ ๊ธธ์ด๊ฐ 3๋ฏธํฐ์ด๋ฏ๋ก ํ ๋ฒ์ ํ์ธํธ์น ์ ์ฐ์๋ 3๊ฐ์ ๊ตฌ์ญ์ ์น ํ ์ ์๊ณ 1, 2, 3๋ฒ ์์ญ์ ํ์ธํธ์น ์ ํ๋ฉด ํ ๋ฒ์ 1, 3๋ฒ ์์ญ์ ๋ชจ๋ ์น ํ ์ ์์ต๋๋ค.๋ฐ๋ผ์ ์ต์ ํ์์ธ 1์ return ํฉ๋๋ค.
์ ์ถ๋ ฅ ์ #3
- ์์ 3๋ฒ์ ๋ชจ๋ ๊ตฌ์ญ์ ํ์ธํธ์น ์ ํด์ผ ํฉ๋๋ค. ๋กค๋ฌ์ ๊ธธ์ด๊ฐ 1๋ฏธํฐ์ด๋ฏ๋ก ํ ๋ฒ์ ํ ๊ตฌ์ญ๋ฐ์ ์น ํ ์ ์์ต๋๋ค. ๊ตฌ์ญ์ด 4๊ฐ์ด๋ฏ๋ก ๊ฐ ๊ตฌ์ญ์ ํ ๋ฒ์ฉ๋ง ์น ํ๋ 4๋ฒ์ด ์ต์ ํ์๊ฐ ๋ฉ๋๋ค.๋ฐ๋ผ์ 4๋ฅผ return ํฉ๋๋ค.
ํ์ด
- ๋น์นธ์ด ์์ผ๋ฉด
- ํ์ธํธ๋ฅผ ์น ํ๊ณ , ๋กค๋ฌ๋ฅผ ์ฎ๊ฒจ๋๋ค.
- ๋น์นธ์ด ์์ผ๋ฉด
- ๊ณ์ ํ์
- ํ์ ํ๋ค ๋ค์ ๋น์นธ์ด ๋์๋๋ฐ ๋กค๋ฌ๊ฐ ๋ค์ ์๋ค?
- ๊ทธ๋ฌ๋ฉด ๋กค๋ฌ๋ฅผ ๊ฐ์ ธ์์ ๋ค์ ์์น .
- ์ด์ฐจํผ ๋ค๋ก ๋๊ฐ๋ ์๊ด์๋๊ฒ, ๊ฒน์ณ์ ์์น ํด๋ ๋๋ค๊ณ ํ๊ธฐ ๋๋ฌธ...
- ๋ง์ฝ ๊ฒน์ณ์ ์น ํ ์ ์๋ค ๊ทธ๋ฌ์ผ๋ฉด, ์์น ๋ถ๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ ๊ณ์ฐํ์ด์ผ ํ๋๋ฐ
- ๋คํํ ์ฌ์ด ๋ฌธ์ ์๋ค.
def solution(n, m, section):
answer = 0
i = 0
pos = section[0]
while i < len(section) and pos <= n:
if pos <= section[i]:
pos = section[i] + m
answer += 1
else:
i += 1
return answer
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (5.89ms, 11.9MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.00ms, 12.9MB)
ํ
์คํธ 3 ใ ํต๊ณผ (5.35ms, 11.9MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.19ms, 10MB)
ํ
์คํธ 5 ใ ํต๊ณผ (7.14ms, 11.6MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.00ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.10ms, 10MB)
ํ
์คํธ 8 ใ ํต๊ณผ (7.20ms, 11.1MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 10 ใ ํต๊ณผ (5.37ms, 11.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 12 ใ ํต๊ณผ (16.68ms, 11MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.00ms, 12.7MB)
ํ
์คํธ 14 ใ ํต๊ณผ (6.64ms, 11.8MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 16 ใ ํต๊ณผ (5.13ms, 10.8MB)
ํ
์คํธ 17 ใ ํต๊ณผ (11.41ms, 11.6MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.06ms, 10.4MB)
ํ
์คํธ 19 ใ ํต๊ณผ (6.13ms, 11.7MB)
ํ
์คํธ 20 ใ ํต๊ณผ (5.76ms, 11MB)
ํ
์คํธ 21 ใ ํต๊ณผ (4.79ms, 11.6MB)
ํ
์คํธ 22 ใ ํต๊ณผ (5.90ms, 11.9MB)
ํ
์คํธ 23 ใ ํต๊ณผ (5.34ms, 12MB)
ํ
์คํธ 24 ใ ํต๊ณผ (0.05ms, 10.1MB)
ํ
์คํธ 25 ใ ํต๊ณผ (10.97ms, 11.5MB)
ํ
์คํธ 26 ใ ํต๊ณผ (2.92ms, 10.9MB)
ํ
์คํธ 27 ใ ํต๊ณผ (0.95ms, 10.4MB)
ํ
์คํธ 28 ใ ํต๊ณผ (0.13ms, 10.3MB)
ํ
์คํธ 29 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 30 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 31 ใ ํต๊ณผ (0.16ms, 10.2MB)
ํ
์คํธ 32 ใ ํต๊ณผ (0.15ms, 10.2MB)
ํ
์คํธ 33 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 34 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 35 ใ ํต๊ณผ (10.75ms, 11.6MB)
ํ
์คํธ 36 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 37 ใ ํต๊ณผ (2.71ms, 10.8MB)
ํ
์คํธ 38 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 39 ใ ํต๊ณผ (3.26ms, 11.1MB)
ํ
์คํธ 40 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 41 ใ ํต๊ณผ (0.00ms, 12.8MB)
ํ
์คํธ 42 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 43 ใ ํต๊ณผ (0.14ms, 10.1MB)
ํ
์คํธ 44 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 45 ใ ํต๊ณผ (5.31ms, 12.2MB)
ํ
์คํธ 46 ใ ํต๊ณผ (0.70ms, 10.3MB)
ํ
์คํธ 47 ใ ํต๊ณผ (6.61ms, 12.3MB)
ํ
์คํธ 48 ใ ํต๊ณผ (2.58ms, 10.8MB)
ํ
์คํธ 49 ใ ํต๊ณผ (3.09ms, 11.3MB)
ํ
์คํธ 50 ใ ํต๊ณผ (5.92ms, 11.9MB)
- ๊ณ ์์ ์ฝ๋
- ์... ์์ ๊น๋ํ๋ค.
def solution(n, m, section):
answer = 1
prev = section[0]
for sec in section:
if sec - prev >= m:
prev = sec
answer += 1
return answer
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (2.45ms, 11.9MB)
ํ
์คํธ 2 ใ ํต๊ณผ (3.90ms, 12.9MB)
ํ
์คํธ 3 ใ ํต๊ณผ (3.54ms, 11.6MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.02ms, 10MB)
ํ
์คํธ 5 ใ ํต๊ณผ (3.03ms, 11.5MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (1.54ms, 11.2MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.02ms, 10MB)
ํ
์คํธ 10 ใ ํต๊ณผ (2.06ms, 11.4MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 12 ใ ํต๊ณผ (2.55ms, 10.9MB)
ํ
์คํธ 13 ใ ํต๊ณผ (6.10ms, 12.8MB)
ํ
์คํธ 14 ใ ํต๊ณผ (4.12ms, 11.8MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.00ms, 9.93MB)
ํ
์คํธ 16 ใ ํต๊ณผ (1.24ms, 10.9MB)
ํ
์คํธ 17 ใ ํต๊ณผ (3.87ms, 11.5MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 19 ใ ํต๊ณผ (2.52ms, 11.8MB)
ํ
์คํธ 20 ใ ํต๊ณผ (1.26ms, 10.9MB)
ํ
์คํธ 21 ใ ํต๊ณผ (2.68ms, 11.6MB)
ํ
์คํธ 22 ใ ํต๊ณผ (3.08ms, 11.8MB)
ํ
์คํธ 23 ใ ํต๊ณผ (3.89ms, 12MB)
ํ
์คํธ 24 ใ ํต๊ณผ (0.01ms, 10MB)
ํ
์คํธ 25 ใ ํต๊ณผ (3.33ms, 11.9MB)
ํ
์คํธ 26 ใ ํต๊ณผ (1.30ms, 10.8MB)
ํ
์คํธ 27 ใ ํต๊ณผ (0.62ms, 10.2MB)
ํ
์คํธ 28 ใ ํต๊ณผ (0.04ms, 10MB)
ํ
์คํธ 29 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 30 ใ ํต๊ณผ (0.02ms, 9.99MB)
ํ
์คํธ 31 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 32 ใ ํต๊ณผ (0.06ms, 10.1MB)
ํ
์คํธ 33 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 34 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 35 ใ ํต๊ณผ (2.88ms, 11.6MB)
ํ
์คํธ 36 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 37 ใ ํต๊ณผ (1.65ms, 10.8MB)
ํ
์คํธ 38 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 39 ใ ํต๊ณผ (1.55ms, 11MB)
ํ
์คํธ 40 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํ
์คํธ 41 ใ ํต๊ณผ (5.10ms, 12.9MB)
ํ
์คํธ 42 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 43 ใ ํต๊ณผ (0.02ms, 10.4MB)
ํ
์คํธ 44 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 45 ใ ํต๊ณผ (2.23ms, 12.1MB)
ํ
์คํธ 46 ใ ํต๊ณผ (0.32ms, 10.5MB)
ํ
์คํธ 47 ใ ํต๊ณผ (4.64ms, 12.3MB)
ํ
์คํธ 48 ใ ํต๊ณผ (0.92ms, 10.8MB)
ํ
์คํธ 49 ใ ํต๊ณผ (2.75ms, 11.1MB)
ํ
์คํธ 50 ใ ํต๊ณผ (2.89ms, 11.9MB)