๐๋ชฉํ : ํ๋ฃจ 1๋ฌธ์ ์ด์ ํ๊ธฐ๐
์ ํ๋ณ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด ์ ์ฅ์์ ๋๋ค.
๋ฐฑ์ค, ํ๋ก๊ทธ๋๋จธ์ค, ๋ฆฌํธ์ฝ๋, ํด์ปค๋ญํฌ ๋ฑ ์๊ณ ๋ฆฌ์ฆ ์ฌ์ดํธ์ ๋ฌธ์ ํ์ด๋ฅผ ์ฌ๋ฆฝ๋๋ค.
๐๋์ด๋๐
๋ฐฑ์ค : Silver ~ Gold
ํ๋ก๊ทธ๋๋จธ์ค : level1 ~ level3
Greedy | Data Structure | Strings | Implementation | DFS BFS | Search | DP | Codeforces
- ๋ฐฑ์ค11047 ๋์ 0 ๋ฌธ์ ย |ย ํ์ด
- ๋ฐฑ์ค11399 ATM ๋ฌธ์ ย |ย ํ์ด
- ๋ฐฑ์ค14659 ํ์กฐ์์ด์ ๋ฆฌํ๊ณ ์ดใ
ใ
๋ฌธ์ ย |ย ํ์ด
๊ฐ๋จํด ๋ณด์์ง๋ง ์ด์ค for๋ฌธ์ผ๋ก ๋ฐฐ์ด์ ์ํํ๋๋ก ์์ฑํ๋๋ ์๊ฐ์ด๊ณผ ์๋ฌ๊ฐ ๋ฌ๋ค.
highest ๊ฐ์ ๋ณ๊ฒฝํ๋ ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋ค. - ๋ฐฑ์ค 1931 ํ์์ค ๋ฐฐ์ ๋ฌธ์ ย |ย ํ์ด
ํ์์ค์ ์ข ๋ฃ์๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํด์ผํ๋ค๋ ๊ฒ๊ณผ, ์ด์ ํ์์ ์ข ๋ฃ์๊ฐ๊ณผ ๋ค์ํ์์ ์์์๊ฐ์ ๋น๊ตํด์ผํ๋ค๋ ๊ฒ๊น์ง๋ ์ ๊ทผํ์ผ๋, ์ด๋ป๊ฒ ๊ตฌ์ฑํด์ผ ํ๋์ง ์์ง ์ด๋ ค์์ด ์์ด ์ธํฐ๋ท์ ์ฐธ๊ณ ํ๋ค.
์ฐธ๊ณ ๋ก bufferedReader๋ฅผ ์ฌ์ฉํ์ ๋์ Scanner๋ฅผ ์ฌ์ฉํ์ ๋ ๋๋ฐฐ ์ฐจ์ด์ ์๊ฐ์ด ๋ฌ๋ค. ๋ง์ ์๋ฅผ ์ ๋ ฅ๋ฐ์ ๋๋ bufferedReader๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ข์ ๊ฒ ๊ฐ๋ค. ์ด ๋ฌธ์ ๋ฅผ ํตํด StringTokenizer์ ์ฌ์ฉ๋ฒ๋ ์ตํ๋ค. - ๋ฐฑ์ค 1541 ์์ด๋ฒ๋ฆฐ ๊ดํธ ๋ฌธ์ ย |ย ํ์ด
์ต์๊ฐ์ด ๋์ค๋ ค๋ฉด ์ต๋ํ ๋ง์ ๋ง์ ์ ํ ํ ์ฐจ๋ก๋๋ก ๋บ์ ์ ํ๋ฉด ๋๋ค.
๋จผ์ -๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ถ๋ฆฌ ํ +๊ธฐํธ๋ก ์ฐ๊ฒฐ๋ ๋ชจ๋ ์ ์๋ฅผ ๋ํ ํ ์ฐจ๋ก๋ก ๋นผ๋ ํ์ด๋ฅผ ํ๋ค.
์ฒซ๋ฒ์งธ ์ซ์์ ๊ธฐ์ค์ ์ 0์ผ๋ก ํด์ ํ๋ ธ๋๋ฐ, ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ด์ฉํด 6์๋ฆฌ ์ด์์ ์ ์๋ก ์ค์ ํ๋ ํด๊ฒฐ๋์๋ค. - ๋ฐฑ์ค 1026 ๋ณด๋ฌผ ๋ฌธ์ ย |ย ํ์ด
B์ ์ต๋๊ฐ๊ณผ A์ ์ต์๊ฐ์ ๊ณฑํ๋๋ก ๋ง๋ค์๋ค.
A๋ฅผ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํ A๋ฅผ ์ํํ๋ฉด์, B์์ ์ต๋๊ฐ(Collections.max() ์ด์ฉ)์ ์ฐพ์ ๊ณฑํ๊ณ B์ ์์๋ฅผ ์ ๊ฑฐํ๋ ๋ฐฉ์์ผ๋ก ์ ๊ทผํ๋ค. - Programmers ์ฒด์ก๋ณต ๋ฌธ์ ย |ย ํ์ด
์ด ํ์ ์์์ lost๋ฐฐ์ด์ ๊ธธ์ด๋งํผ ๋บ ๊ฐ์ answer๋ก ์ง์ ํ ์ซ์๋ฅผ ๋๋ ค๋๊ฐ๋ค.
ํด์์ ์ ์์ฑํด์ reserve๋ฐฐ์ด ์์๋ค์ ์ถ๊ฐํ๋ค.
์ฌ๋ฒ์ด ์๊ณ ๋์์ ์์ด๋ฒ๋ฆฐ ํ์์ ์ ์ธํ๊ธฐ ์ํด ํด์์ ์ lost์์๊ฐ ์๋์ง ์ฐพ๊ณ ,
์๋ค๋ฉด ์ ์์ ์ ๊ฑฐ, lost๋ฐฐ์ด ์์๋ฅผ -1๋ก ๋์ ํ๋ค.(if๋ฌธ ์ํฅ์ ๋ฐ์ง ์๊ฒํ๊ธฐ์ํจ)
์ด ๋ answer๋ ์ฒ์์ ๋ชจ๋ lostํ์ ์๋งํผ ๋นผ์คฌ๊ธฐ ๋๋ฌธ์ 1 ์ฆ๊ฐ์ํจ๋ค.
๋ค์ lost๋ฐฐ์ด์ ์ํํ๋ฉฐ, ํด๋น ์์์ ์, ๋ค(+-1)๊ฐ์ด ์ ๊ณผ ์ผ์นํ๋ฉด
answer๋ฅผ 1์ฆ๊ฐ, set์์ ์ ๊ฑฐํ๋ค.
์ํ๊ฐ ๋๋๋ฉด answer๋ฅผ ๋ฐํํ๋ค.
+) ์ฒ์์ ํด์์ ๋์ ์ด๋ ์ด๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋๋ฐ, remove๋ฉ์๋๋ฅผ ์ฌ์ฉํ ๋
ํด๋น ๊ฐ์ ์ฐพ์์ ์ง์ฐ๋๊ฒ ์๋ ์ธ๋ฑ์ค๊ฐ์ผ๋ก ์ ๊ฑฐํด์ ๋ฐํ์์๋ฌ๊ฐ ๋ฌ๋ค.
+) ํ ์คํธ ์ผ์ด์ค ์ค ์ ๋ ฌ์ด ์๋์ฑ๋ก ์ ๋ ฅ์ด ๋ค์ด์ค๋ ๊ฒฝ์ฐ๊ฐ ์๊ธฐ ๋๋ฌธ์
lost๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ ํ ์งํํ๋ค. - Programmers ๋จ์์นด๋ฉ๋ผ ๋ฌธ์ ย |ย ํ์ด
๊ณ ์๋๋ก์์ ๋๊ฐ ์ง์ (routes[n][1])์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํ,
์ง์ ์ฐจ๋์ ๋๊ฐ์ง์ ๊ณผ ๋ค์ ์ฐจ๋์ ์ง์ ์ง์ ์ ๋น๊ตํด๋๊ฐ๋ฉด ๋๋ค.
๋๊ฐ์ง์ ์ด ์ง์ ์ง์ ๋ณด๋ค ์์๊ฒฝ์ฐ, ๋ ์ฐจ๋์ ๊ฒน์น์ง ์๊ธฐ ๋๋ฌธ์
์นด๋ฉ๋ผ๋ฅผ ํ ๋ ์ถ๊ฐํด์ผํ๋ค.(answer++)
๋๊ฐ๊ณผ ์์๊ฐ์ ๋น๊ตํด์ผํ๋ค๋ ์ ๊ทผ๋ฒ์ด ๋ฐฑ์ค 'ํ์์ค ๋ฐฐ์ '๋ฌธ์ ์ ์ ์ฌํ๋ค.
์ด๋ค ๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํด์ผ ํ๋์ง๊ฐ ํฌ์ธํธ์ธ ๋ฌธ์ . - ๋ฐฑ์ค 1715 ์นด๋ ์ ๋ ฌํ๊ธฐ ๋ฌธ์ ย |ย ํ์ด
๊ทธ๋ฆฌ๋ ๋ฌธ์ ์๊ณผ ๋์์ ์ฐ์ ์์ ํ๋ฅผ ์ด์ฉํ๋ ์๋ฃ๊ตฌ์กฐ ๋ฌธ์ ์ด๊ธฐ๋ ํ๋ค.
๋ฌถ์์ ์ต์ ๋น๊ต์๋ ์์ ๋ฌถ์ ์์๋๋ก ํฉ์น๋ฉด ๋๋ค.
์นด๋๋ฌถ์์ ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๊ธฐ ์ํด ์ฃผ์ด์ง ์์๋ค์ ์ฐ์ ์์ ํ์ ๋ฃ๋๋ค.
ํ์์ ๋ ๋ฌถ์์ ๊บผ๋ด ํฉํ ์๋ฅผ ์ ๋ต๋ณ์์ ๋ํ๊ณ , ๊ทธ ๊ฐ์ ๋ค์ ํ์ ์ง์ด๋ฃ๋๋ค.
์ด ๊ณผ์ ์ ํ์ ์ฌ์ด์ฆ๊ฐ 1์ด ๋ ๋๊น์ง ๋ฐ๋ณตํ๋ค.
ํด๋น ๋ฌธ์ ์ n๊ฐ ๋ฒ์๊ฐ 100,000์ด์ด์, int๋ก ์ ์ธํ๋ฉด ์ ๋ต์ด int๋ฒ์๋ฅผ ์ด๊ณผํ ์ ์๋ค.
๋ฐ๋ผ์ longํ์ ์ผ๋ก ์ ์ธํด์ผํ๋ค. - ๋ฐฑ์ค 2839 ์คํ ๋ฐฐ๋ฌ ๋ฌธ์ ย |ย ํ์ด
์ต์ ๋ด์ง๊ฐฏ์๋ ์ต๋ํ ๋ง์ด 5ํฌ๋ก๊ทธ๋จ์ ๋ด๋ ๊ฒฝ์ฐ์ด๋ค.
๋จผ์ ๊ฐฏ์๋ฅผ ์ธ๊ธฐ ์ํ ์นด์ดํธ๋ณ์๋ฅผ ๋ง๋ ๋ค.
์ฃผ์ด์ง ์๊ฐ 5๋ก๋๋์ด ๋จ์ด์ง๋ฉด ์นด์ดํธ์ ์ถ๊ฐํ๊ณ ์ถ๋ ฅํ๋ค.
๋๋์ด ๋จ์ด์ง์ง ์์ผ๋ฉด 3ํฌ๋ก๊ทธ๋จ์ ๋ด์์ผํ๋ 3์ ๋บ๋ค.
์ด ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
๋ง์ฝ ์ฃผ์ด์ง ์(n)์ด ์์๊ฐ ๋ ๋๊น์ง ๋ฐ๋ณต๋ฌธ์ ํ์ถํ์ง ๋ชปํ๋ค๋ฉด
3๊ณผ 5๋ก ๋ง๋ค ์ ์๋ค๋ ๋ป์ด๋ฏ๋ก -1์ ์ถ๋ ฅํ๋ค.
- ๋ฐฑ์ค10828 ์คํ ๋ฌธ์ ย |ย ํ์ด
python์์๋ stack์ ๋ฐ๋ก ์ ๊ณตํ์ง ์๊ณ , list๋ก ๊ตฌํํ๋ค.
push = append() ๋ฉ์๋
pop = pop() ๋ฉ์๋(์ ๊ฑฐ๋ง ํ๋ฏ๋ก, ์ถ๋ ฅ๋ฌธ์ ๋ฐ๋ก ์ ์ด์ฃผ์ด์ผํ๋ค.)
top = ์ธ๋ฑ์ค[-1]์ ์ด์ฉ
isempty() = python์์ if [๋ฐฐ์ด]์ ํ ๊ฒฝ์ฐ, ๋ฐฐ์ด์ ์์๊ฐ ๋ค์ด์์ผ๋ฉด true๋ฅผ ๋ฐํํ๋ ๊ฒ์ ์ด์ฉ. - ๋ฐฑ์ค10845 ํ ๋ฌธ์ ย |ย ํ์ด
collections ๋ชจ๋์ deque ์ด์ฉ
- LeetCode Find Pivot Index ๋ฌธ์ ย |ย ํ์ด
๋ฐฐ์ด์ ์ํํ๋ฉฐ ์ธ๋ฑ์ค ๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ ํฉ์ด ๊ฐ์ผ๋ฉด ์ธ๋ฑ์ค๊ฐ์ ๋ฐํํ๋๋ก ์์ฑํ๋ค.
- LeetCode Two Sum ๋ฌธ์ ย |ย ํ์ด
- Programmers ๋ก๋์ ์ต๊ณ ์์์ ์ต์ ์์ ๋ฌธ์ ย |ย ํ์ด
์ง์์ง ์ซ์์ ๊ณ ์ ๋ ๋น์ฒจ ๋ฒํธ๋ฅผ ๊ฐ๊ฐ ์นด์ดํธ ํ, ์ต๊ณ ์์๋ ์ง์์ง ์ซ์๊ฐ ๋ชจ๋ ๋น์ฒจ๋ฒํธ์ผ ๋, ์ต์ ์์๋ ์ง์์ง ์ซ์๊ฐ ๋ชจ๋ ๋น์ฒจ๋ฒํธ๊ฐ ์๋ ๊ฒฝ์ฐ๋ก ๋๋
๊ทธ๋๋ก ์์๋ฅผ ์ถ๋ ฅํ๋ฉด ๋๋ ๋ฌธ์ . - Programmers ์ ํ๋ฒํธ ๋ชฉ๋ก ๋ฌธ์ ย |ย ํ์ด
๊ฐ๋จํด ๋ณด์์ง๋ง ํจ์จ์ฑ ํ ์คํธ์์ ๋ฐ๋ชฉ์ด ์กํ ๊ณ ๋ฏผํ๋ ๋ฌธ์ .
๋ฐฐ์ด์ ์ ๋ ฌํ๋ ๊ฒ์ด ํฌ์ธํธ์๋ค.
๋ฌธ์์ด์ ์ ๋ ฌ์ ์ฌ์ ์ ๋๋ก ์ ๋ ฌ๋๋ ๊ฒ์ ํํธ์ผ์ ์ผ๋จ ๋ฐฐ์ด์ ์ ๋ ฌ ํ, ๋ฐฐ์ด์ ๋์์๋ถํฐ indexOf()๋ฉ์๋๋ก ๋น๊ตํด๋๊ฐ๋ค.
์ฒซ๊ธ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ๋๊ธฐ ๋๋ฌธ์ ์ด์ค for๋ฌธ์ผ๋ก ๋ฐฐ์ด์ ๊ฐ๊ฐ ์ํํ ํ์๊ฐ ์์ด์ง๋ค. - Programmers ๋ฒ ์คํธ์จ๋ฒ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ๋์์๋ ๋ชจ๋ ์๊ตฌ์กฐ๊ฑด์ ์ถฉ์กฑํ๋๋ฐ ์ผ๋ถ ํ ์คํธ ์ผ์ด์ค๊ฐ ํต๊ณผ๊ฐ ์๋๋ค. (2022.04.12)
2022.04.13 ํด๊ฒฐ
์์ธ : line 36 songs์ ๊ฐ์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๋, songs.get()๋ฉ์๋์ ํค๊ฐ์ genres์ ์์๋ก ๋ฃ์๊ธฐ ๋๋ฌธ
ํด๊ฒฐ๋ฐฉ๋ฒ : songs์ keySet๋ง ๋ฐ๋ก ๋ฝ์๋ด get๋ฉ์๋์ ํค๋ก ๋ฃ์ด์ค ํ ์ ๋ ฌ.(forEach() ์ฌ์ฉ) - ๋ฐฑ์ค11652 ์นด๋ ๋ฌธ์ ย |ย ํ์ด
์ฃผ์ด์ง ์ ์์ ๋ฒ์๊ฐ int๋ฅผ ์ด๊ณผํ๋ฏ๋ก, long์ผ๋ก ์ ์ธํด์ผ ํ๋ค.
๋ง์ง๋ง ์ ์๊ฐ ๊ฐ์ฅ ๋ง์ด ๋์ฌ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ฐ๋ณต๋ฌธ ์ดํ์ ๋น๊ตํ๋ ์ฝ๋๋ฅผ ํ๋ฒ ๋ ๋ฃ์ด์ฃผ์ด์ผ ํจ.
๋ณ์์ ์ด๊ธฐํ ์กฐ๊ฑด๊ณผ ๋ฐ๋ก๋ฅผ ์ฐพ์๋ด๋ ๊ฒ์ด ์กฐ๊ธ ๊น๋ค๋ก์ ๋ ๋ฌธ์ . - Programmers ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์ ๋ฌธ์ ย |ย ํ์ด
์คํ์ ํน์ง์ ์ ๊ทน์ด์ฉํ๋ ๋ฌธ์ .
0์ด ์๋๊ฒฝ์ฐ ํด๋น ๊ฐ๊ณผ ์คํ์ ๋ค์ด์๋ ๊ฐ์ ๋น๊ตํด ๊ฐ์ผ๋ฉด pop, ๋ค๋ฅด๋ฉด pushํด์ฃผ์๋ค.
๋น์ด์๋ ์คํ์์ peekํ ๊ฒฝ์ฐ EmptyStackException์ด ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ ์์ธ์ฒ๋ฆฌ๋ฅผ ํด์ฃผ์ด์ผ ํ๋ค.
์ด ๋ฌธ์ ์์ ์คํ์ 0์ด ๋ค์ด์ฌ ์ผ์ด ์์ผ๋ฏ๋ก, ์ด๊ธฐ๊ฐ์ผ๋ก 0์ ๋ฃ์ด์ฃผ๋ ๊ฒ์ผ๋ก ์์ธ๋ฅผ ์ฒ๋ฆฌํ๋ค. - Programmers ์คํ์ฑํ
๋ฐฉ ๋ฌธ์ ย |ย ํ์ด
ํด์๋งต์ ํน์ง(๊ฐ์ ํค๋ฅผ ๊ฐ์ง๋ ๊ฐ์ด ๋ค์ด์ค๋ฉด ๋์ค์ ๋ค์ด์ค๋ ๊ฐ์ผ๋ก ๋์ฒด๋จ)์ ์ด์ฉํ๋ฉด change๋ ๋ฐ๋ก ์ ๊ฒฝ์ฐ์ง ์์๋ ๋๋ค.
ํด์๋งต์ record ์์๋๋ก key = id, value = ๋๋ค์์ผ๋ก ๋ฐ๊ณ , leave์ enter์ ๋ง๊ฒ ๋ฉ์์ง๋ฅผ ์ถ๋ ฅํ๋ค. - Programmers ๊ฐ์ฅ ํฐ ์ ๋ฌธ์ ย |ย ํ์ด
'์ ํ๋ฒํธ ๋ชฉ๋ก' ๋ฌธ์ ์ ๋ง์ฐฌ๊ฐ์ง๋ก, ์ ์๋ฅผ ์ฌ์ ์ญ์์ผ๋ก ์ ๋ ฌํ๋ ๊ฒ์ด ํฌ์ธํธ์ธ ๋ฌธ์ .
๋จ, ์กฐ๊ฑด์ด ํ ๊ฐ์ง ๋ ์๋๋ฐ, ์ ์ถ๋ ฅ ์์ ์ค 3, 30๊ณผ ๊ฐ์ ์ซ์๊ฐ ๋ค์ด์ค๋ฉด 330์ด ์๋ 303์ผ๋ก ์ ๋ ฌ๋์ด์ Comparator๋ฅผ ์ฌ์ฉํด ๋ฐ๋ก ์ ๋ ฌํด์ฃผ์ด์ผํ๋ค.
Comparator ์ฌ์ฉ์ ์์ ํ๋๋ฅผ ๋น๊ตํ๋ ๊ฒ์ด ์๋ ๋ ๊ฐ๋ฅผ ๋ํ ๊ฐ์ ๋น๊ตํ๋ฉด ํด๊ฒฐํ ์ ์๋ค.
(๋ฌธ์์ด์์์ + ์ฐ์ฐ์๋ ๋ฌธ์์ฐ๊ฒฐ ์ฐ์ฐ์์์ ์ด์ฉ) - Programmers ์์ฅ ๋ฌธ์ ย |ย ํ์ด
ํด์๋ฅผ ์ฌ์ฉํ๋ฉด ๊ฐ๋จํ๊ฒ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ .
์ ๊ทผ ์์ฒด๋ ์ด๋ ต์ง ์์ผ๋ ์กฐํฉ ๊ณต์์ ๋ํ ์ฌ์ ์ง์์ด ์์ผ๋ฉด ์กฐํฉ์ ๊ณ์ฐํ๋ ์์ ์ฐพ๊ธฐ ํ๋ ๋ฌธ์ ๋ค...
์ข ๋ฅ๋ณ ์ท ๊ฐ์๋ฅผ ๊ฐ๊ฐ answer์ ๊ณฑํด์ฃผ๋๋ฐ, ์ด ๋ ํด๋น ์ข ๋ฅ์ ์ท์ ์ ํํ์ง ์์ ๊ฒฝ์ฐ์ ์ 1์ ํฌํจํด ๊ฐ์+1์ ๊ณฑํด์ฃผ์ด์ผ ํ๋ค.
๋ง์ง๋ง์ผ๋ก ๋ชจ๋ ์ท์ ์ ์ง ์์์ ๊ฒฝ์ฐ 1์ ๋บ ๊ฐ์ returnํ๋ค.
๋๋ ํด์๋งต์ value๋ก Stringํ์ Set์ ์ง์ ํ์ง๋ง, ๋ฌธ์ ์์ ์ด๋ฆ์ด ์ค์ํ์ง ์๊ณ ๊ตฌ๋ถ๋ง ํ๋ฉด ๋๋ฏ๋ก,
๊ตณ์ด set์ ๋ด์ง ์๊ณ Integer๋ก ์ซ์๋ง ํ์ํ๋ ๋ฐฉ๋ฒ์ ํํ ์ฌ๋๋ค์ด ๋ง์๋ค.
plus) forEach()๋ฉ์๋์์ ์ง์ญ๋ณ์๋ฅผ ์ฌ์ฉํ ๋,
๋๋ค์ ๋ด๋ถ๋ ์ต๋ช ๊ตฌํ๊ฐ์ฒด์ด๋ฏ๋ก ์ง์ญ๋ณ์์ ํ๋ผ๋ฏธํฐ๋ก ์ฌ์ฉํ๋ ๋ณ์๋ฅผ ๊ตฌ๋ถํ์ง ๋ชปํ๋ค.
(์ง์ญ๋ณ์๋ฅผ ์์์ ์ผ๋ก ์ฌ์ฉํ๋ผ๋ ์ปดํ์ผ ์ค๋ฅ๊ฐ ๋ฐ์)
ํด๊ฒฐ๋ฐฉ๋ฒ์ ์ง์ญ๋ณ์๋ฅผ ํด๋์ค์ ํ๋๋ก ์ ์ธํ๋ฉด ๋๋ค. - ๋ฐฑ์ค 10773 ์ ๋ก ๋ฌธ์ ย |ย ํ์ด
์คํ์ ์๋ฅผ ์ฐจ๋ก๋ก ๋ด๊ณ 0์ด ๋์ฌ ๊ฒฝ์ฐ pop, ์คํ์ ๋จ์์๋ ์๋ค์ ๋ชจ๋ ๋ํด ๊ฒฐ๊ณผ๊ฐ์ผ๋ก ์ถ๋ ฅํ๋ค.
- ๋ฐฑ์ค 9012 ๊ดํธ ๋ฌธ์ ย |ย ํ์ด
์คํ์ ์์ฑํ๊ณ ์กฐ๊ฑด์ ๋ถ์ฌํ๋ค.
(1) ์คํ์ด ๋น์ด์์ผ๋ฉด push
(2) ์คํ์์ peekํ ๊ฐ์ด '('์ด๊ณ , ๋น๊ตํ ๊ฐ์ด ')'์ด๋ฉด pop
(3) (2)์ ์กฐ๊ฑด์ ์ถฉ์กฑํ์ง ๋ชปํ๋ฉด push
๋ฐ๋ณต๋ฌธ ์ดํ์ ์คํ์ด ๋น์ด์์ผ๋ฉด ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ด๋ค. - Programmers ์ฃผ์๊ฐ๊ฒฉ ๋ฌธ์ ย |ย ํ์ด
์ด์คfor๋ฌธ์ ์ฌ์ฉํ๊ณ , inner for๋ฌธ์ ์์์ธ๋ฑ์ค๋ outer for๋ฌธ์ i+1(i์ ๋ค์ ์ธ๋ฑ์ค)๋ถํฐ ๋น๊ตํ๋๋ก ์ง์ ํ๋ค.
second๋ฅผ 1์ฉ ์ฆ๊ฐ์ํค๋ค๊ฐ ๋น๊ต๋์์ด ๋ ์์ ๊ฒฝ์ฐ์ breakํ๊ณ answer ๋ฐฐ์ด์ ๋ด๋๋ค.
์ดํ second ์ด๊ธฐํ, ๋ฐ๋ณต
์คํ/ํ ๋ฌธ์ ์ง์ ์๋ ๋ฌธ์ ์ธ๋ฐ, ๊ตณ์ด ์ฌ์ฉํ ํ์๋ฅผ ๋ชป๋๊ปด ๊ธฐ๋ณธํ์ ๋ฐฐ์ด์ ์ฌ์ฉํ๋ค. - Programmers ํ๋ฆฐํฐ ๋ฌธ์ ย |ย ํ์ด
์ฐ์ ์์ ํ๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ .
์ฐ์ ์์ ํ๋ ํ์ ์ ๋ ฌ์ด ์ถ๊ฐ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ์ด ๋ฌธ์ ์์ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ์ ์ฌ์ฉํ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ค.
(1) ํ์์ peekํ ๊ฐ๊ณผ priorities ๋ฐฐ์ด์ ์์๋ฅผ ๋น๊ตํ๋ค.
(2) ๊ทธ ๊ฐ์ด ๊ฐ๋ค๋ฉด pollํ๊ณ answer์นด์ดํธ๋ฅผ 1 ์ฆ๊ฐํ๋ค.
(3) ๊ฐ์ด ๊ฐ์ผ๋ฉด์ ์ธ๋ฑ์ค(for๋ฌธ์ i)์ location์ด ์ผ์นํ๋ฉด answer๋ฅผ ๋ฆฌํดํ๋ค. - Programmers ๊ธฐ๋ฅ๊ฐ๋ฐ ๋ฌธ์ ย |ย ํ์ด
ํ๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ .
(1) ๊ฐ ์์ ์ด ๋๋๋ ๋ ์ง๋ฅผ ๋ฏธ๋ฆฌ ๊ณ์ฐํด์ ํ์ ์ ์ฅํ๋ค.
(2) ์ฒซ๋ฒ์งธ ๊ฐ์ ๊บผ๋ด ์์๋ณ์ tmp์ ์ ์ฅํ๊ณ , peekํ ๊ฐ์ด tmp๋ณด๋ค ํด ๋๊น์ง ์นด์ดํธ๋ฅผ ์ฆ๊ฐ์ํค๊ณ , ๊ฐ์ pollํ๋ค.
(3) ํ๊ฐ ๋น ๋๊น์ง 1, 2๋ฅผ ๋ฐ๋ณตํ๋ค. - Programmers ์ด์ค์ฐ์ ์์ํ ๋ฌธ์ ย |ย ํ์ด
2๊ฐ์ ์ฐ์ ์์ํ๋ฅผ ์์ฑํ๋ค. ํ๋๋ ์ค๋ฆ์ฐจ์, ํ๋๋ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค.
I๋ก ์์ํ๋ ์ฐ์ฐ์ด ์์ผ๋ฉด ๋ ํ์ ๋ชจ๋ ์ถ๊ฐํ๋ค.
์ต๋๊ฐ์ ์ ๊ฑฐํ๋ D1์ ๋ง๋๋ฉด maxQ์์ pollํ์ฌ ์์๋ฅผ ์ ๊ฑฐํ๋ค.
๋๊ฐ์ง ํ์ ๋ชจ๋ ์์๋ฅผ ์ถ๊ฐํ๊ธฐ ๋๋ฌธ์ minQ์๋ ํด๋น ์์๋ฅผ ์ฐพ์ ์ ๊ฑฐํ๋ค.(remove()๋ฉ์๋ ์ฌ์ฉ)
D -1๋ ๋ง์ฐฌ๊ฐ์ง๋ก minQ์์ pollํ๊ณ ๋์ผํ ๊ฐ์ maxQ์์๋ ์ ๊ฑฐํ๋ค.
์ฐ์ฐ์ ๋ง์น ํ ํ๊ฐ ๋น์ด์์ง ์์ผ๋ฉด minQ์ maxQ์์ pollํ๊ฐ์ answer์ ์ ์ฅ ํ ๋ฆฌํดํ๋ค. - Programmers ๋ ๋งต๊ฒ ๋ฌธ์ ย |ย ํ์ด
์ค๋ฆ์ฐจ์ ์ฐ์ ์์ํ๋ฅผ ์์ฑํ๊ณ ์ค์ฝ๋น ์ง์๋ฅผ ํ์ ๋ฃ๋๋ค.
์ฒซ๋ฒ์งธ ์์๊ฐ K์ด์์ด ๋ ๋๊น์ง ์๋ก์ด ์์ ๊ณต์์ ์ ์ฉํ๋ค.
ํ๋ฒ์ ์ฐ์ฐ์ด ๋๋ ๋๋ง๋ค answer๋ฅผ ์ฆ๊ฐํ๋ค.
๋ง์ฝ ํ์ ์์๊ฐ ํ ๊ฐ ๋จ์๋๋ฐ K๋ฅผ ๋์ง ๋ชปํ๋ค๋ฉด
๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K์ด์์ผ๋ก ๋ง๋ค ์ ์๋ค๋ ๋ป์ด๋ฏ๋ก -1์ ๋ฆฌํดํ๋ค. - ๋ฐฑ์ค 5430 AC ๋ฌธ์ ย |ย ํ์ด
Collections์ reverse()๋ฉ์๋๋ฅผ ์ฌ์ฉํ๋ฉด ๋ฌด์กฐ๊ฑด ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.
์ด ๋ฌธ์ ๋ ์๋ฐฉํฅ์์ ์ ๊ทผ ๊ฐ๋ฅํ ๋ฑ(deque)๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ ๋ก,
๊ตณ์ด ๋ฐฐ์ด์ ๋ค์ง์ ํ์ ์์ด boolean๋ณ์๋ฅผ ๋ง๋ค๊ณ reverse๊ฐ true๋ฉด pollLast(),
์ ๋ฐฉํฅ์ด๋ฉด pollFirst()ํ๋ฉด ๋๋ค.
๋ก์ง์ ๊ฐ๋จํ๋ ์ ์ถ๋ ฅ์ด ๋งค์ฐ ๋ถ์น์ ํ๊ณ ์์ธ์ฒ๋ฆฌํ ๊ฒ์ด ๋ง์์ ์ฌ๊ธฐ์ ์๊ฐ์ ๋ ์์ ๋ฌธ์ .
(1) ์๋ฌ ์ถ๋ ฅ์ ์ฆ์ ํด๋น ํ ์คํธ ์ผ์ด์ค๋ฅผ ์ข ๋ฃํ๊ณ ์๋ฌ๋ฌธ๊ตฌ๋ ์ผ์ด์ค๋น ํ๋ฒ๋ง ์ถ๋ ฅ. ๋ผ๋ฒจ๋ง์ ์ด์ฉํ๋ค.
(2) ๋ฐฐ์ดํ์์ผ๋ก ์ถ๋ ฅํ ๋ ๋ง์ง๋ง ์์๋ ๋ฐ์ ์ ๋ถ์ด์ง ์๊ณ ์ถ๋ ฅ
(3) ๋ต์ด ๋น๋ฐฐ์ด์ ๋ฐํํ ๊ฒฝ์ฐ [] ์ด๋ ๊ฒ ๋น๋ฐฐ์ด๋ก ์ถ๋ ฅํด์ผํจ - ๋ฐฑ์ค 17219 ๋น๋ฐ๋ฒํธ ์ฐพ๊ธฐ ๋ฌธ์ ย |ย ํ์ด
ํด์๋งต์ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํด์ ํค๊ฐ์ ์ ๋ ฅํ ํ ํด๋น ํค์ ๋ง๋ ๊ฐ์ ๋ฐํํ๋ค.
- ๋ฐฑ์ค 1927 ์ต์ ํ ๋ฌธ์ ย |ย ํ์ด, 11279 ์ต๋ ํ ๋ฌธ์ ย |ย ํ์ด
์ฐ์ ์์ํ๋ฅผ ์์ฑํ๊ณ ํ๋์ฉ ํ์ ์ง์ด๋ฃ๋๋ค.
(์ต์ ํ ๋ฌธ์ ๋ ์ค๋ฆ์ฐจ์, ์ต๋ ํ ๋ฌธ์ ๋ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์์ฑ)
ํ๊ฐ ๋น์ด์๋๋ฐ 0์ด ๋ค์ด์ฌ๊ฒฝ์ฐ 0์ ์ถ๋ ฅํ๊ณ , ๊ทธ ์ธ์๋ poll()ํ์ฌ ์ต์/์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 1991 ํธ๋ฆฌ ์ํ ๋ฌธ์ ย |ย ํ์ด
์ด์ง ํธ๋ฆฌ๋ฅผ ์ ์, ์ค์, ํ์ ์ํํ ์์๋ฅผ ๊ฐ๊ฐ ์ถ๋ ฅํ๋ ๋ฌธ์
Nodeํด๋์ค์ charํ์ rootํ๋๋ฅผ ๋ง๋ค๊ณ , Nodeํ์ left, rightํ๋๋ฅผ ๋ง๋ ๋ค.
์ ๋ ฅ๋ฐ์ ๋ ธ๋๊ฐฏ์๋งํผ์ ํฌ๊ธฐ๋ก Nodeํ์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ , ์ํ๋ฒณ ์์๋๋ก ๋ ธ๋๊ฐ์ฒด๋ฅผ ์ด๊ธฐํํ๋ค.
charํ์ ๋ ธ๋๋ฅผ ์ ์๋ณํ(-'A')ํ ๊ฐ์ ๋ ธ๋๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ก ํ์ํ๊ณ , ๋ ธ๋์ ํด๋นํ๋ left, rightํ๋๋ฅผ ๊ฐ๊ฐ ์ด๊ธฐํํด์ค๋ค.
์ด ๋ ์ ๋ ฅ์ผ๋ก '.'์ด ๋ค์ด์ฌ๊ฒฝ์ฐ null๋ก ์ด๊ธฐํํ๋ค.
์ ์(root-left-right), ์ค์(left-root-right), ํ์(left-right-root) ์์๋๋ก ํ์ํ๋ ๋ฉ์๋๋ฅผ ๊ฐ๊ฐ ์์ฑํ๋ค.
์ฌ๊ท๋ฅผ ์ด์ฉํ๊ณ , ๊ฐ ํ์์์์ ๋ง๊ฒ ์ฝ๋์ ์์๋ฅผ ์กฐ์ ํ๋ค.
ํ์๊ฒฐ๊ณผ๋ฅผ stringbuilder์ ๋ด์ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 1021 ํ์ ํ๋ ํ ๋ฌธ์ ย |ย ํ์ด
์๋ฐฉํฅ์์ ์ ๊ทผํ๋ ๋ฑ์ ์ด์ฉํ๋ ๋ฌธ์
์๋๋ Deque ์ธํฐํ์ด์ค๋ฅผ ์ฌ์ฉํ์ผ๋, ๋ฌธ์ ์์ ์ธ๋ฑ์ค ๊ฐ์ ์ฐพ์์ผ ํ๊ธฐ ๋๋ฌธ์
LinkedList ๊ตฌํํด๋์ค์ indexOf ๋ฉ์๋๋ฅผ ์ด์ฉํ๋ค.
์ฐพ๋ ์๋ฅผ 1๋ฒ์ฐ์ฐ์ ์ํํ ์ ์์ ๋๊น์ง ์ด๋์ํค๋ ๊ฒ
(์๋ฅผ ๋ฝ๋ ์ฐ์ฐ์ ์ค์ง 1๋ฒ๋ง ๊ฐ๋ฅ)์ด ์ต์ข ๋ชฉํ์ด๋ค.
์ต์๊ฐ์ ๊ตฌํ๊ธฐ ์ํด ์ค๊ฐ ์ธ๋ฑ์ค ๊ฐ์ ๊ตฌํด์ผ ํ๋ค.
์ค๊ฐ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์ ์์ผ๋ฉด 2๋ฒ ์ฐ์ฐ,
์ค๋ฅธ์ชฝ์ ์์ผ๋ฉด 3๋ฒ ์ฐ์ฐ์ ์๊ฐ ๋งจ ์์ ์์นํ ๋๊น์ง ๋ฐ๋ณตํ๋ค.
์ฐพ๋ ์๋ฅผ ํ์ ์ ์ฅํด์ ํ๊ฐ ๋น ๋๊น์ง ๋ฐ๋ณตํ๋ค.
ํ๋ฒ ์๋ฅผ ์ฐพ๊ณ ๋๋ฉด ๋ฑ์ ์ฌ์ด์ฆ์ ํ๊ฒ ์ธ๋ฑ์ค, ์ค๊ฐ์ธ๋ฑ์ค๊ฐ์ด ๋ชจ๋ ๋ฐ๋๋ฏ๋ก ์๋กญ๊ฒ ์ ์ฅํ ํ ์นด์ดํธ๋ฅผ ์ผ๋ค. - Programmers ํ๋ฒ๊ฑฐ ๋ง๋ค๊ธฐ ๋ฌธ์ ย |ย ํ์ด
๋ฐฐ์ด์ ๋ฌธ์์ด๋ก ๋ณํ ํ ํ๋ฒ๊ฑฐ๋ฅผ ๋ง๋ค ์ ์์ ๋๊น์ง ๋น๊ตํ๋ฉฐ ๋ฐ๋ณตํ๋ค.
์์ฑ๋ ํ๋ฒ๊ฑฐ๋ ๋ฌธ์์ด์์ ์ ๊ฑฐํ๋ค.
๋ฌธ์์ด๋ก ํ ๊ฒฝ์ฐ ์๊ฐ์ด๊ณผ์ ๋งค์ฐ ์ ์ํด์ผํ๋ค.
๋ฌธ์์ด์ ์คํธ๋ง๋น๋๋ก ์์ฑํ๊ณ ,
์ ๊ฑฐํ ๋ฌธ์์ด์ ์ฌํ ๋นํ๋ ๋์ ๋น๋ ์์ฒด์์ deleteํ๋ค.
๋ํ replace, remove, indexOf ๋์ substring์ ์ด์ฉํ๋ค.
๋์ผํ ๊ฒฐ๊ณผ์ฌ๋ ๋ก์ง์ ๋ฐ๋ผ ์๊ฐ์ฐจ์ด๊ฐ ๋ง์ด ๋ฌ๋ค.
- HackerRank Anagrams ๋ฌธ์ ย |ย ํ์ด
์ปฌ๋ ์ Arrays๋ฅผ import ํ์ง ๋ชปํ๊ฒ ๋์ด์๋ค.
ascii ์ฝ๋๊ฐ์ ์ด์ฉํด a-z ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ ํด๋นํ๋ ์ํ๋ฒณ ์๋ฅผ ์นด์ดํ ํ์ฌ ์ ์ฅ, ๋ ๋ฐฐ์ด์ ์์๋ฅผ ๋น๊ตํ๋๋ก ๋ง๋ค์๋ค. - ๋ฐฑ์ค 20291 ํ์ผ ์ ๋ฆฌ ๋ฌธ์ ย |ย ํ์ด
String Tokenizer๋ฅผ ์ด์ฉํด .์ ๊ธฐ์ค์ผ๋ก ๋ถ๋ฆฌ ํ,
์ฌ์ ์์ผ๋ก ์ถ๋ ฅํ๊ธฐ ์ํด ๋ฐฐ์ด์ ์ ๋ ฌํ๊ณ ์นด์ดํธ ํด์ฃผ์๋ค. - ๋ฐฑ์ค 1543 ๋ฌธ์ ๊ฒ์ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์์ด์์ ์ฃผ์ด์ง ๋จ์ด๋ฅผ ํฌํจํ๋ ๊ฐฏ์๋ฅผ ์ฐพ๋ ๋ฌธ์ .
๋น ๋ฌธ์์ด์ ํ๋ ์์ฑํ๊ณ charAt()๋ฉ์๋๋ฅผ ์ฌ์ฉํด ๋ฌธ์๋ฅผ ํ๋ํ๋ ๋ด๋ค๊ฐ, ํด๋น ๋จ์ด๋ฅผ ํฌํจํ๋ฉด ์นด์ดํธํ๊ณ ๋ฌธ์์ด์ ์ด๊ธฐํ ํด์ฃผ์๋ค. - ๋ฐฑ์ค 15904 UCPC๋ ๋ฌด์์ ์ฝ์์ผ๊น? ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์์ด์ ์ชผ๊ฐ์ ๋ฆฌ์คํธ์ ๋ด๊ณ , ๋ฆฌ์คํธ๋ฅผ ์ํํ๋ฉด์ ์ฐจ๋ก๋๋ก U, C, P, C๋ฅผ ์ฐพ์๋๋ค.
isValid๋ผ๋ intํ์ ๋ณ์๋ฅผ ์ ์ธํ๊ณ ๊ฐ์ ๋ณ๊ฒฝํ๋ฉด์, ๋ฌธ์๊ฐ ์ผ์นํ๊ณ ๋์์ isValid ๊ฐ์ด ์ผ์นํ๋ ๋ฌธ์๊ฐ ์๋์ง ์ฐพ์๋ค.
์ด๋ UCPC๋ผ๋ ๋ฌธ์ ์์๊ฐ ๋ฐ๋๋ฉด ์๋๊ธฐ ๋๋ฌธ์ ์ถ๊ฐ๋ก ์กฐ๊ฑด์ ๋ง๋ ๊ฒ์ด๋ค. - ๋ฐฑ์ค 5525 IOIOI ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์์ด Pn์ ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํด ๋ง๋ค์๋ค.
์ด ๋ฌธ์ ๋ ๋ก์ง์๋ ๋ฌธ์ ๊ฐ ์์ผ๋, ์๊ฐ๋ณต์ก๋ ๋๋ฌธ์ 50์ ์ผ๋ก ๋์จ๋ค.
๋ฌธ์์ด์ ๋น๊ตํ๊ธฐ ์ํด ๋ฐฐ์ด์์ ํ์นธํ์นธ ์ฎ๊ฒจ๊ฐ๋ฉฐ ๋น๊ตํ๋ ๋ฐฉ์์ผ๋ก ํ ๊ฒฝ์ฐ ์ ๋ต์ฒ๋ฆฌ๋์ง ์๋๋ค๊ณ ํ๋ค.
์ ๋ต์ฒ๋ฆฌ๋๊ธฐ ์ํด์ KMP์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด์ผ ํ๋ค๊ณ ํ๋ค.
KMP์๊ณ ๋ฆฌ์ฆ์ด๋ ์ ๋์ฌ(prefix)์ ์ ๋ฏธ์ฌ(suffix)๊ฐ ๊ฐ์ ๋ถ๋ถ ๋ฌธ์์ด ์ค ์ต๋ ๊ธธ์ด๋ฅผ ์ฐพ๊ณ ,
๋ค์ ๋ฌธ์์ด์ ๋น๊ตํ ๋ ๊ทธ ์ ๋ฏธ์ฌ์ ๋ค์์์๋ถํฐ ๋น๊ตํ๋ฉด ๋์ด
ํจ์ฌ ๋น ๋ฅด๊ฒ ๋ฌธ์์ด์ ์ฐพ์ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ํ๋ค.
๋์ค์ KMP์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด ๋ค์ ํ์ด๋ด์ผ๊ฒ ๋ค. - Programmers ์ซ์ ๋ฌธ์์ด๊ณผ ์๋จ์ด ๋ฌธ์ ย |ย ํ์ดย |ย ๋ค๋ฅธ์ฌ๋์ ํ์ด
๋ฌธ์์ด์ charAt()์ผ๋ก ํ๋์ฉ ๋ด๊ณ switch expression์ ์ด์ฉ, ์๋จ์ด๊ฐ ์์ฑ๋๊ฑฐ๋ ์ซ์๊ฐ ๋ค์ด์ค๋ฉด ํด๋นํ๋ ์ซ์๋ก ๋ฐํํด์ฃผ์๋ค.
๋ ๋ฒ์งธ ํ์ด๋ ๋ค๋ฅธ์ฌ๋์ ํ์ด์ธ๋ฐ, replaceAll()์ ์ฌ์ฉํ ๊ฒ์ด ์ธ์๊น์๋ค. - Programmers ์ ๊ท ์์ด๋ ์ถ์ฒ ๋ฌธ์ ย |ย ํ์ด
๋จ์ํ ๋ฌธ์ ์์ ์๊ตฌํ๋ ๋๋ก ์ฐจ๊ทผ์ฐจ๊ทผ ๊ตฌํํ๊ธฐ๋ง ํ๋ฉด ๋๋ ๋ฌธ์ .
์คํ์ ์ฌ์ฉํ๋ฉด ํธํ ๊ฒ ๊ฐ์ ์คํ์ผ๋ก ํ์๋ค.
1๋จ๊ณ์์ ํน์๋ฌธ์๋ฅผ ๋ณํํ ๋ ์ ๊ท์์ ์ด์ฉํ ํ์ด๊ฐ ๋ง์๋ค. ์์ง ์ ๊ท์์ ๋ชฐ๋ผ์ ๋ฐฐ์ด์ ํ์ฉ๋์ง ์๋ ํน์๋ฌธ์๋ค์ ๋ด๊ณ replaceAll์ ์ฌ์ฉํ๋ค. - Programmers [1์ฐจ]๋ด์ค ํด๋ฌ์คํฐ๋ง ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์์ด์ ๋ค์ค์งํฉ์ผ๋ก ๋ง๋ค๊ณ , ์์ด๊ฐ ์๋ ๋ฌธ์๊ฐ ํฌํจ๋ ์์๋ค์ ์ ๊ฑฐํด์ค ๋ค ์ ์ฌ๋๋ฅผ ๊ณ์ฐํ๋ฉด ๋๋ค. ascii์ฝ๋๊ฐ์ ์ด์ฉํ๋ค.
๊ต์งํฉ, ํฉ์งํฉ์ ์์์ ๊ฐฏ์๋ง ๊ตฌํ๋ฉด ๋์ด ๋ฐ๋ก ์งํฉ์ ๋ง๋ค ํ์๊ฐ ์๋ค.
๋์๋ฌธ์๋ง ๋ค๋ฅด๊ณ ๊ฐ์ ๋ฌธ์์ด์ด ๋ค์ด์ฌ ๊ฒฝ์ฐ ์ ์ฌ๋๊ฐ 1์ด๋ฏ๋ก ๊ณ์ฐํ ํ์ ์์ด ๊ทธ๋๋ก ๋ฆฌํดํด์ฃผ๋ฉด ๋๋ค.(๋ฌธ์ ์์๋ 65536) - Programmers ๋ฌธ์์ด ์์ถ ๋ฌธ์ ย |ย ํ์ด
์๋ฅธ ๋ฌธ์์ด์ ๋น๊ตํด๊ฐ๋ zipStr๋ฉ์๋๋ฅผ ๋ง๋ค๊ณ , ๋งค๊ฐ๋ณ์๋ก ๊ธธ์ด(amount)๋ฅผ ์ง์ ํ๋ค.
์ด๊ธฐ๊ฐ์ผ๋ก 0๋ถํฐ amount๊น์ง ์๋ฅธ ๋ฌธ์์ด์ ์ ์ฅํ๊ณ , s์ ๊ธธ์ด๋งํผ ๋ฐ๋ณตํ๋ฉฐ ๋น๊ตํ๋ค.
์ด ๋ ๋ฐ๋ณต๋ฌธ์ ์ฆ๊ฐ์์ amount๋ฅผ ๋ํด์ค๋ค.
๋ฌธ์์ด์ด ๋์ผํ๋ฉด zipCount๊ฐ์ ์ฆ๊ฐํ๋ค๊ฐ ๋ค๋ฅด๋ฉด ๋น๊ต๋ฌธ์์ด(compare)๋ฅผ ํด๋น ๋ฌธ์์ด๋ก ๋์ ํ๊ณ ,
zipCount๊ฐ๊ณผ ๊ธฐ์กด ์๋ฅธ๋ฌธ์์ด์ StringBuilder์ ์ ์ฅํ๋ค.
s์ ๊ธธ์ด๊ฐ amount๋ก ๋๋์ด ๋จ์ด์ง์ง ์์ผ๋ฉด ๋ฐ๋ณต๋ฌธ์ ์ฆ๊ฐ์(i + amount)์์ ์ธ๋ฑ์ค์๋ฌ๊ฐ ๋๋ค.
i + amount๊ฐ์ด s๊ธธ์ด๋ฅผ ์ด๊ณผํ๋ฉด ๋ฐ๋ณต๋ฌธ์ ํ์ถํ๋ ์กฐ๊ฑด์ ๊ฑธ์ด์ฃผ๊ณ ,
๋จ์ ๋ฌธ์์ด์ ์ ์ฅํด๋๋ค๊ฐ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ถ๊ฐํด์ค๋ค.
ํ ์คํธ ์ผ์ด์ค ์ค, ๊ธธ์ด๊ฐ 1์ธ ๋ฌธ์์ด์ด ๋ค์ด์ค๋ ๊ฒฝ์ฐ๊ฐ ์๋ค.
์ด๋ฅผ ๋๋นํด ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ 1์ด๋ฉด ๋ฐ๋ก 1์ ๋ฆฌํดํ๋ ์กฐ๊ฑด์ ๊ฑธ์ด์ฃผ์๋ค.
- ๋ฐฑ์ค 17478 ์ฌ๊ทํจ์๊ฐ ๋ญ๊ฐ์? ๋ฌธ์ ย |ย ํ์ด
์ฌ๊ทํจ์(์๊ธฐ์์ ์ ํธ์ถํ๋ ํจ์)๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ .
์ฌ๊ทํจ์๋ฅผ ์ฒ์ ์ด์ฉํด๋ณธ ๋ฌธ์ . Dashline์ ๊ธธ์ด ๋๋ฌธ์ ํจ์๋ฅผ ๋๊ฐ๋ก ๋๋ ์ ํ์์ง๋ง,
๋์๊ฐ ์์ ๊ฒฝ์ฐ์ write ์ค๊ฐ์ ํจ์๋ฅผ ํธ์ถํ๋ ๋ฐฉ๋ฒ์ผ๋ก ์์ฑํ๋ฉด ๊ฐ๋จํ๊ฒ ์์ฑ๊ฐ๋ฅํ๋ค.
voidํ์ ํจ์์์ ๋ฆฌํด ๊ฐ ์์ด return๋ง ์์ฑํ๋ฉด ํจ์๋ฅผ ํธ์ถํ๋ ๊ณณ์ผ๋ก ๋์๊ฐ๋ค. - Programmers ์์ ๋ํ๊ธฐ ๋ฌธ์ ย |ย ํ์ด
- Programmers K๋ฒ์งธ์ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์์ ์๊ตฌํ๋ ๊ทธ๋๋ก ๊ตฌํํ๋ฉด ๋๋ค.
Arrays.copyOfRange ๋ฉ์๋๋ฅผ ์ฌ์ฉํ๋ฉด ๊ฐ๋จํ๊ฒ ๋ฐฐ์ด์ ์ฌ๋ผ์ด์ฑํ ์ ์๋ค. - Programmers ์๋ ์ซ์ ๋ํ๊ธฐ ๋ฌธ์ ย |ย ํ์ด
indexOf()๋ฉ์๋๋ฅผ ์ด์ฉํ๊ธฐ ์ํด ์ฃผ์ด์ง ๋ฐฐ์ด์ list์ ๋ด๊ณ ๋น๊ตํ๋ค.
0~9๊น์ง์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ , indexOf๋ฅผ ์ด์ฉํด ๋น๊ตํด๋๊ฐ๋ฉฐ ๊ทธ ๊ฐ์ด -1์ด๋ฉด answer์ ๋ํด์ฃผ์๋ค. - Programmers ์คํฌ์ฒดํฌ level2-1 ํ์ด
์ด์ ์ ํ์๋ ๊ฐ์ฅ ํฐ ์ ๋ฌธ์ ์ ๋์ผํ ๋ฌธ์ ๊ฐ ๋์๋ค. ์ ์๋ฅผ ๋ฌธ์์ด ์ทจ๊ธํด ์ฌ์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋, 3, 30๊ณผ ๊ฐ์ ์ซ์์ฒ๋ผ ์์ธ๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋ ๋ฌธ์์ด์ฉ ๋ฌถ์ด ๋น๊ตํด์ผ ํ๋ค.
- Programmers ์คํฌ์ฒดํฌ level2-2 ํ์ด
2์ฐจ์ ๋ฐฐ์ด์ ์ด์ฉํด ํ๋ ฌ์ ํ์ ํ๋ ๋ฌธ์ .
1์ฐจ์ ๋ฐฐ์ด์์ ๊ฐ์ ๋ฐ๊พธ๋ ์๋ฆฌ์ ๋์ผํ๋ค. ๋ฐ๊พธ๊ธฐ ์ํด ์๋ ๊ฐ์ ์์๋ณ์์ ์ ์ฅํ๊ณ ,
๋ฐฐ์ด์ ์ด๋์ ๋ง์น๋ฉด ๋น ์๋ฆฌ์ ์ ์ฅํด๋์๋ ๊ฐ์ ๋ฃ์ด์ฃผ๋ฉด ๋๋ค.
ํ ๋๋ฆฌ๋ง ํ์ ์ํค๋ฉด ๋๋ฏ๋ก ์ฃผ์ด์ง ์ฟผ๋ฆฌ์ ์์ ํ/์ด, ๋ ํ/์ด ๊ธฐ์ค์ผ๋ก ๊ฐ์ ๋์ ํด๋๊ฐ๋ฉด๋๋ค.
์์ ๊ฐ์ ์์๋ณ์์ ์ ์ฅํ๊ณ , ๋น ์๋ฆฌ๋ถํฐ ์๊ณ๋ฐฉํฅ์ผ๋ก ํ์นธ์ฉ ๋น๊ฒจ์๋ค.
์ฟผ๋ฆฌ ํ๋๋น ์ด 4๋ฒ์ ์ด๋์ด ์ผ์ด๋๊ณ , ๊ทธ๋๋ง๋ค ์ต์๊ฐ์ ๋น๊ตํด min์ ์ ์ฅํ๋ค.
ํ์ ์ ๋ชจ๋ ๋ง์น๋ฉด min๊ฐ์ ๋ฆฌํดํ๊ณ , ๊ทธ ๊ฐ์ answer๋ฐฐ์ด์ ๋ด์ ๋ฆฌํดํ๋ฉด ๋๋ค.
ํด๋น ์ฌ์ดํธ์ ํ๋ ฌ ํ ๋๋ฆฌ ํ์ ํ๊ธฐ ๋ฌธ์ ์ ๋์ผํ๋ค. - ๋ฐฑ์ค 17427 ์ฝ์์ ํฉ 2 ๋ฌธ์ ย |ย ํ์ด
์ผ๋ฐ์ ์ธ ์ฝ์์ ํฉ์ ๊ตฌํ๋ ๋ฐฉ์์ผ๋ก ์ ๊ทผํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.
1๋ถํฐ n๊น์ง์ ์ฝ์๋ฅผ ๋ชจ๋ ๋์ดํ๋ฉด, 1์ด๋์ค๋ ๊ฐฏ์๋ n, 2๊ฐ ๋์ค๋ ๊ฐฏ์๋ (n / 2) * 2, 3์ด ๋์ค๋ ๊ฐฏ์๋ (n / 3) * 3,
์ด๋ ๊ฒ n๊น์ง ์ฆ๊ฐํ๋ ๊ท์น์ ํ์ธํ ์ ์๋ค.
๊ทธ๋๋ก ๊ณต์ํํด์ ๋ชจ๋ ๋ํ ๊ฐ์ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 8979 ์ฌ๋ฆผํฝ ๋ฌธ์ ย |ย ํ์ด
CompareTo ๋ฉ์๋๋ฅผ ์ฌ์ ๋ ฌํด์ผํ๋ ๋ฌธ์ .
๊ตญ๊ฐ๋ณ ์ด๋ฆ, ๊ธ์๋ ๋ฉ๋ฌ ์, ์์๋ฅผ ์ ์ฅํ ํด๋์ค๋ฅผ ๋ง๋ค๊ณ , Comparable ์ธํฐํ์ด์ค๋ฅผ ๊ตฌํํ๊ณ ๋ฉ์๋๋ฅผ ์ค๋ฒ๋ผ์ด๋ํ๋ค.
๋ฉ๋ฌ์ ์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ ํ์๋ฉ๋ฌ ์๋ฅผ ๋น๊ตํด๊ฐ๋ฉฐ ์ ๋ ฌํ๋ค.
์ ๋ ฅ๋ฐ์ ์ ๋ณด๋ฅผ Nation๊ฐ์ฒด์ ์ ์ฅ ํ ArrayList์ ์ถ๊ฐํ๋ค.
๋๊ฐ์ฉ ๋น๊ตํ๋ฉฐ ์์๋ฅผ ์ ํ๋ค. ๋ง์ฝ ๊ธ์๋ ๋ฉ๋ฌ ์๊ฐ ๋ชจ๋ ๊ฐ์ผ๋ฉด ๋ค์ ๊ตญ๊ฐ์ ์์์ ์ด์ ๊ตญ๊ฐ์ ์์๋ฅผ ๋์ ํ๋ค.
๊ฐ์ง ์๋ค๋ฉด ๋ค์ ๊ตญ๊ฐ์ ์์๋ (์ด์ ๊ตญ๊ฐ๋ค์ ํฉ + 1)๋ก ์ ํ๋ค.
์ฌ๊ธฐ์๋ for๋ฌธ์ด 1๋ถํฐ ์์๋๋ก ๋์๊ฐ๊ธฐ ๋๋ฌธ์ i+1๋ก ์ง์ ํ์๋ค. - ๋ฐฑ์ค 3048 ๊ฐ๋ฏธ ๋ฌธ์ ย |ย ํ์ด
๊ฐ๋ฏธ์ ๊ทธ๋ฃน๋ฒํธ์ ์์(์ํ๋ฒณ)์ ์ ์ฅํ๋ Antํด๋์ค๋ฅผ ๋ง๋ ๋ค.
๊ทธ๋ฃน์ ํญ์ ๋๊ฐ์ด๋ฏ๋ก, ์์๋ก 1, 2๋ก ์ง์ ํ๋ค.
๋ฌธ์ ์์ ์ฃผ์ด์ง ์์๋๋ก ์ ๋ ฅ๋ฐ์ ant๊ฐ์ฒด๋ฅผ ์์ฑํ๊ณ , ArrayList์ ์ถ๊ฐํ๋ค.
์๊ฐ์ด 0์ด๋ ๋๊น์ง ๋ฆฌ์คํธ๋ฅผ ์ํํ๋ค.
๊ฐ๋ฏธ ๋๊ฐ์ฉ ๋ฝ์ ๋น๊ตํ๋ค. ๋ง์ฝ ์ด์ ๊ฐ๋ฏธ์ ๊ทธ๋ฃน๊ณผ ๋ค์๊ฐ๋ฏธ์ ๊ทธ๋ฃน์ด ๋ค๋ฅด๋ฉด ์์๋ฅผ ๋ฐ๊ฟ์ค๋ค.
1์ด์ ํ๋ฒ์ฉ๋ง ๊ฐ๋ฏธ๋ฅผ ๋ฐ์ด๋์ผ๋ฏ๋ก, for๋ฌธ์ i๋ฅผ 1 ์ฆ๊ฐํด ๊ฑด๋๋ฐ์ด์ค๋ค.
๋ํ ๊ฐ๋ฏธ๋ ์ ์ง๋ง ํ๋ฏ๋ก, ๊ทธ๋ฃน ํ๋๋ฅผ ๊ธฐ์ค์ผ๋ก ์ก๋ ์กฐ๊ฑด์ ์ถ๊ฐํด์ผํ๋ค.
์ด ์กฐ๊ฑด์ ์ถ๊ฐํ์ง ์์ ์ ๊ทธ๋ฃน์ด ๋ค๋ฅผ ๋๋ง๋ค ๋ณ๊ฒฝ์ด ์ผ์ด๋ ๊ฐ๋ฏธ๊ฐ ๋ค๋ก ๊ฐ ์ ์๋ค. - Programmers [3์ฐจ] ํ์ผ๋ช
์ ๋ ฌ ๋ฌธ์ ย |ย ํ์ด
Comparable ์ธํฐํ์ด์ค๋ฅผ ๊ตฌํํด์ผํ๋ ์ ๋ ฌ๋ฌธ์
head, number, tails๋ฅผ ์ ์ฅํ๋ Files ํด๋์ค๋ฅผ ๋ง๋ค๊ณ compareTo ๋ฉ์๋๋ฅผ ์ค๋ฒ๋ผ์ด๋ฉํ์ฌ ์กฐ๊ฑด์ ๋ง๊ฒ ์ ๋ ฌํ๋ค.
์ด ๋ head๋ ๋์๋ฌธ์๋ฅผ ๊ตฌ๋ถํ์ง ์์ผ๋ฏ๋ก ๋ชจ๋ ์๋ฌธ์(or ๋๋ฌธ์)์ฒ๋ฆฌ ํ ๋น๊ตํ๋ค.
ํ์ ์๋ณธString๊ฐ์ ๊ทธ๋๋ก ๋ฐํํด์ผํ๊ธฐ ๋๋ฌธ์ number์ ๊ฒฝ์ฐ numberIntํ๋์ ์ ์๋ณํํ number๋ฅผ ์ ์ฅํ๊ณ ,
์๋ณธ number๋์ numberInt๋ฅผ ์ฌ์ฉํ์ฌ ์ ๋ ฌํ๋ค.
๋ฌธ์์ด์ ๋ฐ์์ ์ ๊ทํํ์์ ์ด์ฉํด splitํ head, number๊ฐ์ ์ป๋๋ค.
tail์ head์ number ๋ค ๋๋จธ์ง ๋ชจ๋ ๋ฌธ์์ด์ด๋ฏ๋ก ๋์ length๋ฅผ ๋ํ ๊ฐ์ substring์ beginning๊ฐ์ผ๋ก ์ง์ ํ๋ค.
Files๊ฐ์ฒด๋ฅผ ์์ฑํํ Filesํ์ ๋ฐฐ์ด์ ์์๋๋ก ์ ์ฅํ๋ค.
Arrays.sort๋ก ์ฌ์ ๋ ฌํ ๋ฉ์๋๋ฅผ ์ฌ์ฉํด ์ ๋ ฌ ํ ์์๋ณต๊ตฌํ ๋ฌธ์์ด์ ๋ฐํํ๊ธฐ ์ํด
๋ฐฐ์ด์ ์ํํ๋ฉฐ ํ๋๊ฐ๋ค์ ์ฐ๊ฒฐ์ํจ ํ answer๋ฐฐ์ด์ ์ถ๊ฐํ๋ค.
+) toString ๋ฉ์๋๋ฅผ ์ค๋ฒ๋ผ์ด๋ฉํ๋ฉด ๋ฉ์๋ ํธ์ถ๋ก ๊ฐ๋จํ๊ฒ ํ๋๋ค์ ์ฐ๊ฒฐํ ์ ์๋ค. - Programmers ๊ฐ์ธ์ ๋ณด ์์ง ์ ํจ๊ธฐ๊ฐ ๋ฌธ์ ย |ย ํ์ด
"ํ ๋ฌ์ ๋ชจ๋ 28์ผ๋ก ๊ฐ์ ํ๋ค" ๊ฐ ์ค์ํ ๋ฌธ์
date๊ฐ์ฒด๋ก ๋ ์ง ๊ณ์ฐ์ ํ๋ค๊ฐ ์ ์กฐ๊ฑด์ ๋ค๋ฆ๊ฒ ๋ณด๊ณ ์๊ฐ์ ๋ ๋ ค๋ฒ๋ ธ๋ค.
๋จ์ํ๊ฒ ์ฃผ์ด์ง ๋ ์ง๋ฅผ 28์ ๊ณฑํ์ฌ ์ผ ์๋ก ํ์ฐํ ํ,
ํ๊ฒ ๋ ์ง์ ๋น๊ตํ์ฌ ๋ง๋ฃ๋ ์ ์ ๋ฒํธ๋ง ๋ฆฌํดํ๋ค.
๊ตณ์ด ํด๋์ค ์์ฑ -> ์ ์ฅ -> ๋น๊ต์ ๊ณผ์ ์ ๊ฑฐ์น์ง ์๊ณ
๋ฐ๋ก ๋ฐฐ์ด์ํํ๋ฉฐ ๋น๊ตํ๋๊ฒ ๋ ๊น๋ํ์ ๋ฏ ํ๋ค.
- Programmers ํ๊ฒ ๋๋ฒ ๋ฌธ์ ย |ย ํ์ด
์ธํฐ๋ท์ ์ฐธ๊ณ ํ ํ์ด.
์ฌ๊ทํจ์๋ฅผ ์ด์ฉํด ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ํ๋ค.
numbers์ ์ธ๋ฑ์ค๋ฅผ 1์ฉ ์ฆ๊ฐ์ํค๋ฉด์ ์ธ๋ฑ์ค์ ํด๋นํ๋ ๊ฐ์ sum์ ๋์ ์ํค๊ณ ,
๊ทธ ๊ฐ์ด target๊ณผ ์ผ์นํ๋ฉด answer๊ฐ์ 1์ฉ ์ฆ๊ฐ์ํจ๋ค.
ํฉ์ ๊ณ์ฐํ๋ dfs์ ๋บ์ ์ ๊ณ์ฐํ๋ dfs๋ฅผ ๊ฐ๊ฐ ํธ์ถํ๋ค. - BFS ์๊ณ ๋ฆฌ์ฆ์ ๋ํ ์ดํด
์ธ์ ํ๋ ฌ๋ก ๊ตฌํํ BFSย |ย ์ธ์ ๋ฆฌ์คํธ๋ก ๊ตฌํํ BFS
BFS๋ ํ๋ก ๊ตฌํํ๊ณ , DFS์ ๋ฌ๋ฆฌ ์ฌ๊ท์ ์ผ๋ก ๋์ํ์ง ์๋๋ค.
2์ฐจ์ ๋ฐฐ์ด(์ธ์ ํ๋ ฌ)๊ณผ ์ธ์ ๋ฆฌ์คํธ๋ก ๊ตฌํํ๋ 2๊ฐ์ง์ ๋ฐฉ๋ฒ์ด ์๋ค.
๊ทธ๋ํ ๋ด์ ์ ์ ์์ ๊ฐ์ ์ ๊ฐ์ง๋ค๋ฉด ์ธ์ ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ ๋ฆฌํ๋ค.(์ธ์ ํ๋ ฌ์ ๊ฒฝ์ฐ ๋ฉ๋ชจ๋ฆฌ ๋ญ๋น๊ฐ ํฌ๊ธฐ ๋๋ฌธ)
๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ์ ์ ์๋ booleanํ์ ๋ฐฐ์ด์ ๊ฐ์ด ์ ์ธํด์ผ ํ๋ค.
์์ ๋ ธ๋๋ฅผ ํ์ ์ ์ฅํ ํ, ํ์์ ๊บผ๋ด(poll) ํด๋น ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด์๋ ๋ ธ๋๋ค์ ๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ์ฒดํฌํ๋ค.
๋ง์ฝ ๋ฐฉ๋ฌธ์ด ์๋ ๋ ธ๋๋ผ๋ฉด, ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํ ํ์ ์ง์ด๋ฃ๋๋ค.
์ด ๊ณผ์ ์ ํ๊ฐ ๋น ๋๊น์ง ๋ฐ๋ณตํ๋ฉด bfsํ์์ด ์๋ฃ๋๋ค. - DFS ์๊ณ ๋ฆฌ์ฆ์ ๋ํ ์ดํด
์ฌ๊ท(recursion)๋ก ๊ตฌํํ DFS
DFS๋ ์ฐ๊ฒฐ๋ ธ๋๋ฅผ ๋ฐ๋ผ์ ๊ณ์ ํ๊ณ ๋ค์ด๊ฐ ํ,
๋์ด์ ์ฐ๊ฒฐ๋ ๋ ธ๋๊ฐ ์๋ค๋ฉด ๋ ธ๋๋ฅผ ์ฐพ์ ๋๊น์ง ์ด์ ๋ ธ๋๋ก ๋๋์๊ฐ๋ค.
์ผ๋ฐ์ ์ผ๋ก DFS๋ ์ฌ๊ท๋ก ๊ตฌํํ๊ณ , stack์ผ๋ก ๊ตฌํํ๋ ๋ฐฉ์๋ ์๋ค.
์ฒ์ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ฉด ๊ทธ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ ธ๋๋ค์ ํ์ํ๋ค.
๋ง์ฝ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋๊ฐ ์๋ค๋ฉด dfs๋ฅผ ๋ค์ ํธ์ถํ๋ค. - ๋ฐฑ์ค 2178 ๋ฏธ๋ก ํ์ ๋ฌธ์ ย |ย ํ์ด
bfs๋ฌธ์
์, ํ, ์ข, ์ฐ๋ก ์ด๋์ด ๊ฐ๋ฅํ์ง ์ฒดํฌํ๊ณ , ์ด๋์ด ๊ฐ๋ฅํ๋ฉด ํด๋น ์ขํ๋ฅผ ํ์ ์ถ๊ฐํ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๋ค.
์ด๋ํ ๋ ์นธ ์๋ฅผ ์ธ์ผํ๋ฏ๋ก, ์ด์ ์ขํ์์ 1์ฉ ์ฆ๊ฐํ๋ฉด์ ์ด๋ํ๋ค.
๋ง์ฝ ์๋ก์ด ์ขํ ๊ฐ์ด 0 ๋ฏธ๋ง์ด๊ฑฐ๋, ๊ทธ๋ํ ํฌ๊ธฐ๋ฅผ ์ด๊ณผํ๋ค๋ฉด continueํด์ค๋ค. - ๋ฐฑ์ค 2606 ๋ฐ์ด๋ฌ์ค ๋ฌธ์ ย |ย ํ์ด
์ฐ๊ฒฐ์ ๋ณด๋ฅผ ๊ทธ๋ํ์ ์ ์ฅํ ํ bfs ํ์ํ๋ค.
์ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ์นด์ดํธ ํ์๋ฅผ 1 ์ฆ๊ฐ์ํจ๋ค. - ๋ฐฑ์ค 2667 ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ ๋ฌธ์ ย |ย ํ์ด
์ด์ฐจ์ ๋ฐฐ์ด์ ์ฐจ๋ก๋ก ์ํํ๋ค๊ฐ
์ง์ด ์กด์ฌํ๊ณ (1), ๋ฐฉ๋ฌธํ ์ ์ด ์์ผ๋ฉด(false) bfs๋ฅผ ํธ์ถํ๋ค.
๋ฏธ๋ก ํ์ ๋ฌธ์ ์ ๋ง์ฐฌ๊ฐ์ง๋ก ์, ํ, ์ข, ์ฐ๋ก ์ด๋์ด ๊ฐ๋ฅํ์ง ์ฒดํฌํ๊ณ ๋ฐฉ๋ฌธํ๋ค.
bfsํจ์๋ฅผ ์์ฑํ ๋ ๋จ์ง ๋ด ์ง์ ๊ฐฏ์๋ฅผ ๋ฐํํ๋๋ก ์นด์ดํธ ๋ณ์๋ฅผ ์ถ๊ฐํ๋ค.
๋ฐํ๋ ์นด์ดํธ๋ฅผ arraylist์ ๋ด๊ณ ๋ชจ๋ ํ์์ด ๋๋๋ฉด ๋ฆฌ์คํธ๋ฅผ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํ ์ถ๋ ฅํ๋ค.
์ด ๋จ์ง ์๋ ๋ฆฌ์คํธ์ ์ฌ์ด์ฆ๋ฅผ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 7569 ํ ๋งํ ๋ฌธ์ ย |ย ํ์ด
3์ฐจ์ ๋ฐฐ์ด์ bfs๋ฅผ ์ ์ฉํ๋ ๋ฌธ์
์ด๋๋ฐฉํฅ์ด ์, ํ, ์ข, ์ฐ, ์, ์๋ ์ด 6๊ฐ์ง์ด๋ค.
๋ฐฐ์ด์ ์ํํ๋ฉด์ ์ต์ํ ๋งํ (1)๊ฐ ์๋ ์ขํ๋ฅผ ์ฐพ์ ํ์ ์ถ๊ฐํ๋ค.
ํ์์ ๋นผ๋ธ ์ขํ์ ์ธ๊ทผ(์, ํ, ์ข, ์ฐ, ์, ์๋)์ ์์ต์ ํ ๋งํ ๊ฐ ์๋์ง ํ์ธํ๊ณ ,
์์ผ๋ฉด ํด๋น ์ขํ๋ฅผ ํ์ ์ถ๊ฐํ๊ณ ์ด์ ์ขํ๊ฐ์์ 1์ฉ ์ฆ๊ฐ์ํจ๋ค.
ํ๊ฐ ๋น ๋๊น์ง ํด๋น ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์ ๋์ ์ผ์๋ฅผ ๋ฐํํด์ผํ๊ธฐ ๋๋ฌธ์ ํ์์ ๋ง์น ๋ฐฐ์ด์์ ์ต๋๊ฐ์ ์ฐพ์ ๋ฆฌํดํ๋ค.
๋ง์ฝ ์์ต์ ํ ๋งํ (0)๊ฐ ํ๋๋ผ๋ ์์ผ๋ฉด -1์ ๋ฐํํ๋ค.
์ฒซ์งธ๋ ์ ์ ์ธํ๊ธฐ ๋๋ฌธ์ result์์ -1ํ ๊ฐ์ด ์ ๋ต์ด๋ค. - ๋ฐฑ์ค 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ ๋ฌธ์ ย |ย ํ์ด
2์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ ๋ฐฐ์ถ๊ฐ ์๋ ๊ณณ์ 1๋ก ์ด๊ธฐํํ๋ค.
๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ํ์ํ๋ boolean๋ฐฐ์ด์ ๋ง๋ค๊ณ ๊ทธ๋ํ๋ฅผ ์ํํ๋ค.
๋ฐฐ์ถ๊ฐ ์๊ณ (1), ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ขํ์ ๋ํด bfs ํ์์ ์ํํ๋ค.
ํ๋ฒ์ ํ์์ด ๋๋ ๋๋ง๋ค ์นด์ดํธ ํ์๋ฅผ ์ฆ๊ฐ์ํจ๋ค.
ํ๋์ ํ ์คํธ ์ผ์ด์ค๊ฐ ๋๋ ๋๋ง๋ค ์นด์ดํธ๋ฅผ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 5014 ์คํํธ๋งํฌ ๋ฌธ์ ย |ย ํ์ด
์ข์ฐ ์ด๋์ด ์๊ณ ์ํ๋ก๋ง ์ด๋ํ๊ธฐ ๋๋ฌธ์ 1์ฐจ์ ๋ฐฐ์ด๋ก ํ ์ ์๋ค.
์๋ฆฌ๋ฒ ์ดํฐ์ ์ธต์๊ฐ 1๋ถํฐ ์์ํ๊ธฐ ๋๋ฌธ์ ๊ฑด๋ฌผ๋์ด+1๋งํผ์ ๋ฐฐ์ด์ ์์ฑํ๋ค.
bfs๋ฅผ ํธ์ถํ๊ณ , ์ฌ๋ผ๊ฐ์ ๋์ ๋ด๋ ค๊ฐ์ ๋๋ฅผ ๊ฐ๊ฐ ํ์ํ๋ค.
๊ฑด๋ฌผ๋ฒ์๋ฅผ ๋ฒ์ด๋์ง ์๊ณ ๋ฐฉ๋ฌธํ์ง ์์ ์ธต(0)์ ํ์ ์ถ๊ฐํ๊ณ ํ์๋ฅผ ์ธ๊ธฐ ์ํด ์ง์ ๋ฐฐ์ด์ ๊ฐ์์ 1์ฉ ์ฆ๊ฐํ๋ค.
ํ์์ pollํ ๊ฐ์ด ๋ชฉ์ ์ง์ธต๊ณผ ๊ฐ์ผ๋ฉด ๋ฆฌํดํ๋ค. ์ด ๋ ์์์ธต์์๋ ๋ฒํผ์ ๋๋ฅด์ง ์๊ธฐ ๋๋ฌธ์ -1ํด์ค๋ค.
๋ชฉ์ ์ง์ธต๊ณผ ์ผ์นํ์ง ์์ผ๋ฉด -1์ ๋ฆฌํดํ๊ณ "use the stairs"๋ฅผ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 1697 ์จ๋ฐ๊ผญ์ง ๋ฌธ์ ย |ย ํ์ด
N, K์ ๋ฒ์๊ฐ 0๋ถํฐ 100,000์ด๊ธฐ ๋๋ฌธ์ ์ต๋๊ฐ+1๋งํผ์ ๋ฐฐ์ด์ ์์ฑํ๋ค.
bfsํ์์ ์ฌ์ฉํ๊ณ , x+1, x-1, 2x์ ๊ฒฝ์ฐ๋ฅผ ๊ฐ๊ฐ ํ์ํ๋ค.
๋ฐฐ์ด์ ๋ฒ์์ ์๊ณ ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์์น(0)์ด๋ผ๋ฉด ํ์ ์ถ๊ฐํ๋ค.
๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํ ๋ ์ด๋ฅผ ์ธ๊ธฐ ์ํด ์ง์ ์์น์ ๊ฐ+1์ ํ๋ค.
๋์์ ์์น์ ํ์ฌ์์น๊ฐ ๊ฐ๋ค๋ฉด ํด๋น ์์น์ ๊ฐ์ ๋ฆฌํดํ๋ค.
์์ ์์น๋ ์ด๋ฅผ ์ธ์ง ์๊ธฐ ๋๋ฌธ์ -1ํ ๊ฐ์ด ์ ๋ต์ด๋ค. - ๋ฐฑ์ค 2468 ์์ ์์ญ ๋ฌธ์ ย |ย ํ์ด
์ ๊ธฐ๋ ๋ฐฐ์ถ ๋ฌธ์ ์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์์ญ์ ๊ฐฏ์๋ฅผ ์ธ๋ ๋ฌธ์ ์ด๋ค.
๋จ, ๊ฐ ๋์ด๋ณ๋ก ๋ฌผ์ ์ ๊ฒผ์ ๋์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋น๊ตํด์ผ ํ๋ค.
๋์ด์ ๋ณด๋ฅผ ์ ์ฅํ๊ธฐ ์ํ set์ ๋ง๋ค๊ณ , ๋ฐฐ์ด์ ์ํํ๋ฉฐ ๋์ด๋ฅผ ์ ์ฅํ๋ค.
set์ ์ฌ์ฉํ ์ด์ ๋ ์ค๋ณต์ ์ ๊ฑฐํ๊ธฐ ์ํจ.
๋ฌธ์ ์กฐ๊ฑด์ "์๋ฌด ์ง์ ๋ ์ ๊ธฐ์ง ์์ ์ ์๋ค"๊ฐ ์๊ธฐ ๋๋ฌธ์ ์ฒ์์ 0์ addํด์ฃผ๊ณ ์์.
๊ฐ ๋์ด๋ฅผ ์ํํ๋ฉด์ ์ขํ๊ฐ ํด๋น ๋์ด๋ณด๋ค ํฌ๊ณ ๋ฐฉ๋ฌธํ์ง ์์์ ๋(false) bfs๋ฅผ ํธ์ถํ๋ค.
bfsํ์์ด ๋๋๋ฉด ์์ ์์ญ์ ์นด์ดํธํ๋ค.
๋์ด ํ๋์ ๋ํ ํ์์ด ๋๋๋ฉด ์์ ์์ญ ์นด์ดํธ์ boolean๋ฐฐ์ด์ ์ด๊ธฐํํด์ค๋ค.
์์ ์์ญ์ ์ต๋๊ฐ์ ๋น๊ตํด์ ์ถ๋ ฅํ๋ค. - Programmers ๋คํธ์ํฌ ๋ฌธ์ ย |ย ํ์ด
bfsํ์์ผ๋ก ํ์๋ค.
์ปดํจํฐ์ ๊ฐฏ์ = ๋ ธ๋์ ๊ฐฏ์๋ผ๊ณ ์๊ฐํ๋ค.
๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ํ์ธํ๊ธฐ ์ํด ๋ ธ๋ ๊ฐฏ์ ํฌ๊ธฐ์ boolean๋ฐฐ์ด์ ์์ฑํ๋ค.
๋ ธ๋๊ฐฏ์๋งํผ ๋ฐ๋ณตํ๋ฉฐ, ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋์ ๋ํด bfsํ์์ ์ํํ๋ค.
bfs๋ด๋ถ์์ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ฉด ์ฐ๊ฒฐ๋ ๋ ธ๋๋ค์ ํ์ํ๋ค.
๋ง์ฝ ์ฐ๊ฒฐ๋ ๋ ธ๋๊ฐ ์๊ณ (1), ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด(false) ํ์ ์ถ๊ฐํ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๋ค.
ํ์์ด ๋๋๋ฉด answer๋ฅผ ์ฆ๊ฐํ๋ค. - ๋ฐฑ์ค 2573 ๋น์ฐ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๊ณผ์ ์ ํฌ๊ฒ ์ชผ๊ฐ์ ์๊ฐํ๋ค.
(1)๋น์ฐ์ ๋ น์ธ๋ค.
(2)๋ น์ธ ๋น์ฐ์์ bfsํ์ํ๋ค.
(3)ํ๋ฒ์ bfsํ์์ด ๋๋๋ฉด area๊ฐฏ์๋ฅผ ์ฆ๊ฐํ๋ค.
(4)1, 2, 3๊ณผ์ ์ area๊ฐฏ์๊ฐ 2์ด์์ด ๋ ๋๊น์ง ๋ฌดํ๋ฐ๋ณตํ๋ค.
(5)while๋ฌธ์์ ํ๋ฒ์ ์ฌ์ดํด์ด ๋๋๋ฉด year๋ฅผ 1 ์ฆ๊ฐํ๊ณ , area์ visited๋ฅผ ์ด๊ธฐํ ํด์ค๋ค.
(6)ํ์ถ์กฐ๊ฑด์ ๋ถํฉํ๋ฉด year์ถ๋ ฅ
(7)๋ง์ฝ ๋น์ฐ์ด ๋ชจ๋ ๋ น์๋ค๋ฉด(๋ชจ๋ 0) 0์ ์ถ๋ ฅ
melt๋ฉ์๋์์๋ 0์ด ์๋ ๋ชจ๋ ์ขํ๋ฅผ ํ์ ๋จผ์ ์ง์ด๋ฃ๊ณ ํ์ํ๋ค.
๋ํ ํ๋์ visited์๋ ๋ค๋ฅธ ๋ ๋ฆฝ์ ์ธ boolean๋ฐฐ์ด์ด ํ์ํ๊ธฐ ๋๋ฌธ์ ๋ฉ์๋ ์์์ ์ ๋ฐฐ์ด์ ์์ฑํ๋ค.
๋๋ ๋ชจ๋ bfsํ์์ผ๋ก ํ์์ง๋ง, ๋ น์ด๋ ๊ณผ์ ์ bfs, ์์ญํ์์ dfs๋ก ํธ๋ ๋ฐฉ์์ด ๊ฐ์ฅ ๋ง์๋ค. - Programmers ๊ฒ์ ๋งต ์ต๋จ๊ฑฐ๋ฆฌ ๋ฌธ์ ย |ย ํ์ด
0, 1๋ก ์ด๋ฃจ์ด์ง nxm ๋ฐฐ์ด์์์ ๋ฏธ๋ก ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์
์ ํ์ ์ธ bfs ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ ๋ฌธ์ ์ด๋ค.
๋จ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ์ง ๋ชปํ ์ -1์ ๋ฆฌํดํ๋ผ๋ ์กฐ๊ฑด์ด ์์๋ค.
- Programmers x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์ ๋ฌธ์ ย |ย ํ์ด
์ฃผ์ํ ์ : ๋ณ์๋ฅผ ์ ์ธํ ๋ longํ์ ์ผ๋ก ๋ง์ถฐ์ค์ผ ์ฌ์ดํธ ํ ์คํธ๋ฅผ ํต๊ณผํ ์ ์๋ค.
- ๋ฐฑ์ค 1339 ๋จ์ด ์ํ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ : ๋ธ๋ฃจํธํฌ์ค ์๊ณ ๋ฆฌ์ฆ
์ํ๋ฒณ ๊ฐฏ์๋งํผ์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ , ๋ฌธ์์ด์ ์๋ฆฟ์๋งํผ 10์ ๊ฑฐ๋ญ์ ๊ณฑ ๊ฐ์ ํด๋น ์ํ๋ฒณ ์๋ฆฌ์ ๋ํ๋ค.(charAt()๊ณผ ascii์ฝ๋๊ฐ ์ด์ฉ)
์์ฑ๋ ๋ฐฐ์ด์ ์ ๋ ฌํ๊ณ ๋ฐฐ์ด์ ๋์์๋ถํฐ ์ฐจ๋ก๋๋ก 9~1์ ๊ณฑํ ๊ฐ์ ๋ํ๋ฉด ๋ฌธ์ ์ ๋ต์ ๊ตฌํ ์ ์๋ค. - ๋ฐฑ์ค 2630 ์์ข
์ด ๋ง๋ค๊ธฐ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ : ๋ถํ ํ์
๋ถํ ํ์์ด๋, ํด๊ฒฐ์ด ์๋๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐ์ด ๋ ๋๊น์ง ๋ถํ ํด์ ํ์ํ๋ ๊ฒ์ด๋ค.
์ฌ๊ท์ ๋ํ ์ดํด๊ฐ ํ์ํ๋ค. ํด๋น ๋ฌธ์ ๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ๊ฑฐ์ณ ํด๊ฒฐํ๋ค.
(1) ๋จผ์ ๋ชจ๋ ์์ด ๊ฐ์์ง๋ฅผ ๋ฐ์ ธ๋ณด๊ณ , ๊ฐ์ผ๋ฉด white/blue์ ๋ํ๋ค.
(2) ๊ฐ์ง ์์ผ๋ฉด 4๋ฑ๋ถํ๊ณ , ๊ฐ๊ฐ 1์ ์ํํ๋ค.
(3) ๋ชจ๋ ์์ข ์ด๊ฐ ์์ฑ๋ ๋๊น์ง 1, 2๋ฅผ ๋ฐ๋ณตํ๋ค.(์ฌ๊ท)
4๋ฑ๋ถ ํ์ ๋ ๊ฐ๊ฐ์ ์ธ๋ฑ์ค ๊ฐ์ x, y์ขํ์์ 4๋ถ๋ฉด์ ๋๋๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ค. - ๋ฐฑ์ค 1992 ์ฟผ๋ํธ๋ฆฌ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ : ๋ถํ ํ์
์์ ์์ข ์ด ๋ง๋ค๊ธฐ ๋ฌธ์ ์ ์์ ํ ๋์ผํ๊ฒ ํ์ดํ๋ฉด ๋๋ค.
์ถ๋ ฅ๋ฐฉ์์๋ง ์ฐจ์ด๊ฐ ์๋ค. ์์ข ์ด๋ ํ์๋ฅผ, ์ด ๋ฌธ์ ๋ ๊ฒฐ๊ณผ ๊ทธ๋๋ก๋ฅผ ์ถ๋ ฅํ๋ฉด ๋๋ค.
์์ถ์ depth๋๋ก ๊ดํธ๋ฅผ ์ง์ ํ๋ ค๋ฉด ์ฌ๊ทํจ์ ํธ์ถ ์ ๊ณผ ํธ์ถ ํ์ ๊ฐ๊ฐ ์ฌ๋ ๊ดํธ์ ๋ซ๋ ๊ดํธ๋ฅผ ๋ฃ์ด์ฃผ๋ฉด ๋๋ค. - ๋ฐฑ์ค 1780 ์ข
์ด์ ๊ฐ์ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ : ๋ถํ ํ์
์์ข ์ด ๋ง๋ค๊ธฐ, ์ฟผ๋ํธ๋ฆฌ์ ๋์ผํ๊ฒ ํ๋ฉด ๋๋ค.
๋จ, ์ด ๋ฌธ์ ์์๋ 9๋ฑ๋ถํ๊ธฐ ๋๋ฌธ์ ์ฌ๊ท๋ฅผ ํธ์ถํ ๋ 9๊ฐ์ ์์ญ์ผ๋ก ๋๋์ด ํธ์ถํด์ผํ๋ค. - Programmers ๋ชจ์๊ณ ์ฌ ๋ฌธ์ ย |ย ํ์ด
๋์ด๋ ์๋ ๋ฌธ์ ๋ ์๋์ง๋ง ์๊ตฌ์ฌํญ ๋๋ก ์์ฑํ๋ค๋ณด๋ ์ ํ ์์์น ๋ชปํ๊ฒ ์ฝ๋๋์ด ๋ง์์ก๋ค..
๋ฐฐ์ด์ ์ฌ์ด์ฆ๋ฅผ ์ ํ๊ธฐ ์ํ ๋ฐ๋ณต๋ฌธ, ๋ต์ ๊ตฌํ ํ์ answer์ ๋ด๊ธฐ ์ํด ํ๋ฒ ๋ ๋ฐ๋ณต๋ฌธ์ ๋๋ฆฌ๋ ๋ฑ
๋ถํ์ํ ์ฝ๋๋ค์ ๋ง์ด ์์ฑํ ๊ฒ ๊ฐ์ ์์ฌ์ด ๋ฌธ์ . - ๋ฐฑ์ค 11659 ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4 ๋ฌธ์ ย |ย ํ์ด
๋์ ํฉ์ ์ด์ฉํ์ง ์์ผ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋๋ ๋ฌธ์ .
๋ฐฐ์ด์ ์ด๊ธฐํํ ๋ ๋์ ํฉ์ ๊ณ์ฐํ ๊ฐ์ ๋ด์์ผ ํ๋ค. ์ด๋ 0๋ฒ์งธ ์ธ๋ฑ์ค๋ ๊ฑด๋๋ฐ๊ณ 1๋ฒ์งธ ์ธ๋ฑ์ค๋ถํฐ ์ ์ฅ
์ธ๋ฒ์งธ ์ค๋ถํฐ (์์, ๋) ๊ตฌ๊ฐ์ด ์ ํด์ง๋ฉด ๋ฐฐ์ด์ ๋์ธ๋ฑ์ค์์ ์์ - 1 ์ธ๋ฑ์ค๋ฅผ ๋บ ๊ฐ์ ๋ฐํ
์์๊ฐ์ ํฌํจํ๊ธฐ ์ํด ์์ - 1์ ํด์ค์ผํ๋ค. - ๋ฐฑ์ค 18870 ์ขํ ์์ถ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ: ์ ๋ ฌ
(1) ๋์ค์ ์๋ณธ๋ฆฌ์คํธ๋ฅผ ํค๋ก ๊ฐ์ ธ์์ผํ๊ธฐ ๋๋ฌธ์ ๋ฆฌ์คํธ๋ฅผ ๋ณต์ฌํ๋ค.
(2) ์์ถ์ขํ๊ฐ์ ์ ์ฅํ ํด์๋งต์ ์์ฑํ๋ค.
(2) ๋ณต์ฌํ ๋ฆฌ์คํธ๋ฅผ ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๊ณ , ํด๋น ํค๊ฐ ์ด๋ฏธ ๋งต์ ์๋์ง ํ์ธ ํ ์์ผ๋ฉด ๋งต์ ์ ์ฅํ๋ค. value๋ 0๋ถํฐ ์ฆ๊ฐ์ํจ๋ค. (3) ์๋ณธ ๋ฆฌ์คํธ๋ฅผ ์ํํ๋ฉฐ ํด๋น ์์์ ํค๊ฐ์ stringbuilder์ ๋ด์ ์ถ๋ ฅํ๋ค. - Programmers ์ฟผ๋์์ถ ํ ๊ฐ์ ์ธ๊ธฐ ๋ฌธ์ ย |ย ํ์ด
์ฟผ๋ํธ๋ฆฌ ์์ถ๋ฐฉ์์ผ๋ก ์์ถํ๋ค.
๋ฐฐ์ด์ ๋ชจ๋ ์์๋ฅผ ๋น๊ตํ๋ฉฐ ๋์ผํ๋ฉด 0, 1์ ๋ฐ๋ผ answer๋ฐฐ์ด์ 1์ฉ ์ฆ๊ฐํ๊ณ ,
๋ค๋ฅด๋ฉด ํฌ๊ธฐ๋ฅผ 4๋ถํ ํ ํ ๋ค์ ์ฒดํฌํ๋ค.(์ฌ๊ทํธ์ถ) - ๋ฐฑ์ค 1436 ์ํ๊ฐ๋
์ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ: ๋ถ๋ฅดํธํฌ์ค
์ซ์๋ฅผ ๊ณ์ ์ฆ๊ฐ์ํค๋ค 666์ด ํฌํจ๋์ด์์ผ๋ฉด ์นด์ดํธํ๋ค.
contains()๋ฉ์๋๋ฅผ ์ด์ฉํ๊ธฐ ์ํด ๋ฌธ์์ด๋ก ๋ณํํ๋ค.
์นด์ดํธ๊ฐ ์ ๋ ฅ๋ฐ์ n๊ณผ ๊ฐ์ผ๋ฉด ์ถ๋ ฅํ๊ณ ๋ฐ๋ณต๋ฌธ์ ํ์ถํ๋ค. - ๋ฐฑ์ค 1920 ์ ์ฐพ๊ธฐ ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ: ์ด๋ถํ์
์ด๋ถํ์์ด๋ ๋ฐ์ผ๋ก ๋๋ ์ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์๋์๋ฆฌ๋ up/down๊ฒ์๊ณผ ์ ์ฌํ๋ค. ์ฐพ์ผ๋ ค๋ ๊ฐ์ ์ค๊ฐ๊ฐ๊ณผ ๋น๊ตํด์ ์์์ง, ํฐ์ง ํ๋ณํด๋๊ฐ๋ฉด ๋๋ค.
์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด ์์ค๋ฐฐ์ด์ ์ ๋ ฌ๋์ด์์ด์ผํ๋ค.
์ค๊ฐ์ธ๋ฑ์ค๋ฅผ ๊ตฌํ ํ ์ฐพ๋ ๊ฐ์ ์ค๊ฐ์ธ๋ฑ์ค๊ฐ๊ณผ ๋น๊ตํ๋ค.
์์ผ๋ฉด ๋์ธ๋ฑ์ค๋ฅผ ์ค๊ฐ - 1
ํฌ๋ฉด ์์์ธ๋ฑ์ค๋ฅผ ์ค๊ฐ + 1
์ผ์นํ๋ฉด ํ์์ด ์ข ๋ฃ๋๋ค.
+- 1์ ํด์ฃผ๋ ์ด์ ๋ ์ค๊ฐ๊ฐ์ด ์ด๋ฏธ ์ผ์นํ์ง ์์ ์ ์ธํ๊ณ ํ์ํ๊ธฐ ์ํจ์ด๋ค.
์ด ๋ฌธ์ ๋ ๊ฐ์ด ์์ผ๋ฉด 1, ์์ผ๋ฉด 0์ ๋ฐํํ๋๋ก ๋์ด์๊ธฐ ๋๋ฌธ์
๋ฉ์๋์์ boolean๊ฐ์ ๋ฐํํ๋๋ก ํ๊ณ ,
๋ฐํ๊ฐ์ด true์ด๋ฉด 1, false์ด๋ฉด 0์ ์ถ๋ ฅํ๋ค. - ๋ฐฑ์ค 10816์ซ์ ์นด๋ 2 ๋ฌธ์ ย |ย ํ์ด
๋ฌธ์ ์ ํ: ์ด๋ถํ์
lowerbound / upperbound์ ๊ฐ๋ ์ด ํ์ํ๋ค.
์ด๋ถํ์์ผ๋ก ์ฐพ๊ณ ์ํ๋ ์์์ ์ํ์ ๊ณผ ํํ์ ์ธ๋ฑ์ค๋ฅผ ๊ตฌํ๋ค.
์ํ์ธ๋ฑ์ค - ํํ์ธ๋ฑ์ค์ ๊ฐ์ด ์ค๋ณต์์์ ๊ฐฏ์๊ฐ ๋๋ค.
ํํ์ธ๋ฑ์ค๋ ํด๋น์์๊ฐ ์์๋๋ ์ธ๋ฑ์ค์ด๊ณ (ํฌํจ),
์ํ์ธ๋ฑ์ค๋ ํด๋น์์๊ฐ ์๋ ์ฒซ ์ธ๋ฑ์ค(ํฌํจx)์ด๋ฏ๋ก
๋์ ์กฐ๊ฑด์์ ๋ค๋ฅด๊ฒ ์ง์ ํด์ผํ๋ค.
- DP ์๊ณ ๋ฆฌ์ฆ์ ๋ํ ์ดํด
DP ์๊ณ ๋ฆฌ์ฆ -> "๊ท์น์ฑ"์ ๋ ์ฌ๋ฆฌ์.
๋ฌธ์ ๋ฅผ ์์ ๋จ์๋ก ์ชผ๊ฐ์ ๊ท์น์ ์ฐพ์๋ด๊ณ , ๊ทธ ๊ท์น์ ์ด์ฉํด ์ ์ฒด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ์์ด๋ค.
Top-down๋ฐฉ์๊ณผ Bottom-up๋ฐฉ์์ด ์๋ค.
ํผ๋ณด๋์น ์์ด์ ๊ตฌํ๋ ๊ฒ์ ์๋ก ๋ค์ด,
Top-down๋ฐฉ์๊ณผ Bottom-up๋ฐฉ์์ผ๋ก ๊ฐ๊ฐ ๊ตฌํํ๋ค.(1)Bottom-up ๋ฐฉ์ = Tabulation
๊ฐ์ฅ ๋ฎ์ ๋จ๊ณ์์ ์์ํด์ ์๋ก ์ฌ๋ผ๊ฐ๋ ๋ฐฉ์
๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํด์ ๊ตฌํํ๋ค.
ํผ๋ณด๋์น ์์ด์์ ๊ฐ์ฅ ๋ฎ์ ๋จ๊ณ๋ F(0) = 0 ๊ณผ F(1) = 1 ์
์ด ๋๊ฐ๋ฅผ ์ด์ฉํด F(2)๋ฅผ ๋ง๋ค๊ณ , ์ด ๊ฒฐ๊ณผ๋ F(3)์ ๋ง๋ค ๋ ์ด์ฉ๋๋ค.
์ด ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด F(n)์ ํผ๋ณด๋์น ์์ด์ ๊ตฌํ ์ ์๋ค.
์ผ๋ฐ์ ์ผ๋ก bottom-up๋ฐฉ์์ด ๋ ๋น ๋ฅด๊ฒ ๋์ํ๋ค.(2)Top-down ๋ฐฉ์ = Memorization
์ฌ๊ท๋ฅผ ์ด์ฉํด ๊ฐ์ฅ ๋ฎ์๋จ๊ณ๊ฐ ๋ ๋๊น์ง ๋ค์ด๊ฐ์ ์ฐพ๋ ๋ฐฉ์์ด๋ค.
์ด ๋, ๋จ์ํ ๋ชจ๋ ๋ ธ๋์ ๋ํด ํ์ํ ๊ฒฝ์ฐ ๋ถํ์ํ ๊ฐ๊น์ง ๋ฐ๋ณตํ๊ฒ๋์ด ์์ฒญ๋๊ฒ ๋นํจ์จ์ ์ด๋ฏ๋ก,
ํ๋ฒ ๊ตฌํ ๊ฐ์ ์ ์ฅํด๋๊ฐ๋ฉด์(memorization) ํ์ํ๋ค.
์ผ๋ฐ์ ์ผ๋ก HashMap์ ์ฌ์ฉํด ์ ์ฅํ๋ค.
Bottom-up ๋ฐฉ์์ ๋นํด ํ์๋ฌธ์ ๋ค์ ํด๊ฒฐํ๊ธฐ ์ํ ๋ ผ๋ฆฌ์ ์ ๋ ฌ๋จ๊ณ๊ฐ ํ์ํ์ง ์์ผ๋ฏ๋ก
๊ตฌํ์ด ๋ ์ฝ๋ค๋ ์ฅ์ ์ด ์๋ค.
- Codeforces Round #784 (Div. 4) (3solved, result : 2 out of 8)
- A ๋ฌธ์ ย |ย ํ์ด
- B ๋ฌธ์ ย |ย ํ์ดย |ย ์ฌํ์ด
๋ฐฐ์ด์ ์ ๋ ฌ ํ ๋ค๋ฅธ ์ ์ ๊ฐ์ด ๋์ฌ ๋๋ง๋ค ์นด์ดํธ ๋ณ์๋ฅผ ์ด๊ธฐํํด์ค๋ค.
3 ์ด์์ด ๋๋ฉด ํด๋น ์๋ฅผ ๋ฐ๋ก ํ๋ฆฐํธ ํด์ฃผ๊ณ ๋น ์ ธ๋์ค๊ฒ ํ๋ค.
3๊ฐ ์ด์์ ๊ฐ์ด ์์ ์์ ๊ฒฝ์ฐ -1์ ํ๋ฆฐํธํด์ฃผ๊ธฐ ์ํด boolean๋ณ์๋ฅผ ๋ง๋ค์๋ค.
๋ฐ๋ณต๋ฌธ ์ดํ์๋ boolean์ด true๋ฉด -1์ ํ๋ฆฐํธํด์ค๋ค.
contest ๋น์์๋ ํต๊ณผ๋์์ผ๋ ๋๋ ํ ํ ์คํธ์ผ์ด์ค๊ฐ ๋ ์ถ๊ฐ๋๋ฉด์ ํ์์์์ผ๋ก ์ธํด ์ค๋ต์ฒ๋ฆฌ ๋์๋ค.(1000ms ์ด๊ณผ)์ฌํ์ด ์๋ฃ(2022.06.03) (249ms)
ํด์๋งต์ ์์ฑํ๋ค. ํค: ์์ / ๊ฐ: ์นด์ดํธ
ํด๋นํ๋ ํค๊ฐ ๋งต์ ์ด๋ฏธ ์์ผ๋ฉด ํด๋นํ๋ ๊ฐ์ ๋ฐ์์จ๋ค.
1 ์ฆ๊ฐํ๊ณ ๋ค์ ๋งต์ ์ถ๊ฐํ๋ค.
๋งต ์ด๊ธฐํ๊ฐ ๋๋ ํ ๊ฐ์ด 3์ด์์ธ ํค๋ฅผ ์ฐพ์ ์ถ๋ ฅํ๋ค.
๋ง์ฝ 3์ด์์ธ ๊ฐ์ด ์์ ๊ฒฝ์ฐ๋ฅผ ๊ตฌ๋ถํ๊ธฐ ์ํด boolean๋ณ์๋ฅผ ๋ง๋ค์๋ค.
notIn์ด true๋ฉด -1์ ์ถ๋ ฅํ๋ค. - C ๋ฌธ์ ย |ย ํ์ด
๋ฐฐ์ด์ ์ง์๋ฒ์งธ์์, ํ์๋ฒ์งธ์์๋ค์ด ๊ฐ๊ฐ ๋ชจ๋ ํ์๊ฑฐ๋ ์ง์์ผ ๊ฒฝ์ฐ YES๊ฐ ๋๋ค.
boolean๋ณ์๋ฅผ 4๊ฐ ๋ง๋ค์ด ์ง์๋ฒ์งธ ์์์ ํ/์ง, ํ์๋ฒ์จฐ ์์์ ํ/์ง์ ๋น๊ตํด YES๊ฐ ๋๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์กฐ๊ฑด์์ผ๋ก ๋์ดํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ค.
๊ฐ์ธ์ ์ผ๋ก ์ ๋ง ๋ฌด์ํ๊ฒ ํ์๋ค๊ณ ์๊ฐํ๋ค... ๋ ์ข์ ํ์ด๋ฒ์ด ์๊ฐ๋๋ฉด ์ถ๊ฐํด์ผ๊ฒ ๋ค.