[programmers] ๋ง์น ํ๊ธฐ - Java
ํ์ธํธ๋ฅผ ๋ค์ ์น ํด์ผ ํ๋ ๊ตฌ์ญ์ ์๋ฅผ ์ต์ํํ๋ ๋ฌธ์ ์์, ๋กค๋ฌ์ ๊ธธ์ด์ ๋ค์ ์น ํด์ผ ํ๋ ๊ตฌ์ญ๋ค์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋๋ค. ๋กค๋ฌ๋ ๋ฒฝ์์ ๋ฒ์ด๋์ง ์๊ณ , ๊ตฌ์ญ์ ์ผ๋ถ๋ถ๋ง ์น ํ ์ ์์ต๋๋ค. ๊ฐ ๊ตฌ์ญ์ ํ ๋ฒ์ฉ ์น ํ๋ฉด์ ํ์ํ ์น์
์ ์๋ฅผ ๊ณ์ฐํ๊ณ , ๊ฐ ์น์
์ ์์๊ณผ ๋์ ๊ฐฑ์ ํ๋ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํฉ๋๋ค.
Mar 27, 2024
๋ง์น ํ๊ธฐ
๋ฌธ์ ์ค๋ช
์ด๋ ํ๊ต์ ํ์ธํธ๊ฐ ์น ํด์ง ๊ธธ์ด๊ฐ
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๋ฒ ์์ญ์ ํ์ธํธ๋ฅผ ๋ค์ ์น ํด์ผ ํฉ๋๋ค. ๋กค๋ฌ์ ๊ธธ์ด๊ฐ 4๋ฏธํฐ์ด๋ฏ๋ก ํ ๋ฒ์ ํ์ธํธ์น ์ ์ฐ์๋ 4๊ฐ์ ๊ตฌ์ญ์ ์น ํ ์ ์๊ณ 1, 2, 3, 4๋ฒ ์์ญ์ ํ์ธํธ์น ์ ํ๋ฉด ํ ๋ฒ์ 1, 3๋ฒ ์์ญ์ ๋ชจ๋ ์น ํ ์ ์์ต๋๋ค.
๋ฐ๋ผ์ ์ต์ ํ์์ธ 1์ return ํฉ๋๋ค.
์
์ถ๋ ฅ ์ #3
- ์์ 3๋ฒ์ ๋ชจ๋ ๊ตฌ์ญ์ ํ์ธํธ์น ์ ํด์ผ ํฉ๋๋ค. ๋กค๋ฌ์ ๊ธธ์ด๊ฐ 1๋ฏธํฐ์ด๋ฏ๋ก ํ ๋ฒ์ ํ ๊ตฌ์ญ๋ฐ์ ์น ํ ์ ์์ต๋๋ค. ๊ตฌ์ญ์ด 4๊ฐ์ด๋ฏ๋ก ๊ฐ ๊ตฌ์ญ์ ํ ๋ฒ์ฉ๋ง ์น ํ๋ 4๋ฒ์ด ์ต์ ํ์๊ฐ ๋ฉ๋๋ค.
๋ฐ๋ผ์ 4๋ฅผ return ํฉ๋๋ค.
solution.java
import java.util.*; class Solution { public int solution(int n, int m, int[] section) { int start = section[0]; int end = section[0] + (m-1); int ans = 1; for(int i : section){ if(i>=start && i<=end) continue; else{ start = i; end = i + (m-1); ans++; } } return ans; } }
ํต์ฌ ํค์๋
start
๋ณ์๋ฅผ ์ฒซ ๋ฒ์งธ ์น์ ์ ์์ ์ธ๋ฑ์ค๋ก ์ด๊ธฐํํ๊ณ ,end
๋ณ์๋ฅผ ์ฒซ ๋ฒ์งธ ์น์ ์ ๋ ์ธ๋ฑ์ค๋ก ์ด๊ธฐํํ๋ค.
- ๋ฐฐ์ด์ ๋ฐ๋ณตํ๋ฉด์ ๊ฐ ์์๋ฅผ ํ์ธํ๋ค.
- ํ์ฌ ์์๊ฐ ํ์ฌ ์น์ ์ ์ํ๋์ง ํ์ธํ๋ค. ์ํ๋ค๋ฉด ๊ฑด๋๋ฐ๊ณ ๋ค์ ์์๋ฅผ ํ์ธํ๋ค.
- ํ์ฌ ์์๊ฐ ํ์ฌ ์น์
์ ์ํ์ง ์๋๋ค๋ฉด, ์๋ก์ด ์น์
์ ์์ํ๊ฒ ๋๋ฏ๋ก
start
๋ฅผ ํ์ฌ ์์์ ์ธ๋ฑ์ค๋ก,end
๋ฅผstart
์์m-1
์ ๋ํ ๊ฐ์ผ๋ก ๊ฐฑ์ ํ๊ณ ,ans
๋ฅผ 1 ์ฆ๊ฐ์ํจ๋ค.
๊ฒฐ๋ก !
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์ฒ์ ์๋ํ๋ ๋ฐฉ์์ ๋จ์ํ section์ ๊ฐ๊ณผ ๊ทธ ๋ค์ ๊ฐ์ ๋น๊ตํด์ ๊ทธ ์ฐจ๊ฐ m๋ณด๋ค ์์ ๊ฒฝ์ฐ ๋ฆฌํดํ ๊ฐ์ ์ฆ๊ฐ์ํค๋ ๋ฐฉ์์ผ๋ก ๊ตฌํํ๋ค. ์ด ๊ฒฝ์ฐ ๋ค์ ์น ํ ๋ ์ฐ์ ์น์
์ฌ์ด์ ๊ฑฐ๋ฆฌ๊ฐ m๋ณด๋ค ํฐ ๊ฒฝ์ฐ๋ฅผ ์ฌ๋ฐ๋ฅด๊ฒ ์ฒ๋ฆฌํ์ง ๋ชปํ๋ค.
์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์
๋ ฅ๋ ๋ฐฐ์ด์ ์น์
์ผ๋ก ๋๋ ๋๋ง๋ค ์๋ก์ด ์น์
์ ์์ํ๊ณ , ๊ฐ ์น์
์ ์์๊ณผ ๋์ ๊ฐฑ์ ํ๋ฉด์ ํ์ํ ์น์
์ ์๋ฅผ ๊ณ์ฐํ๋ ๋ฐฉ์์ ์๋ํ๋ค.
Share article