Java(39)
-
[BOJ] 18870 - ์ขํ ์์ถ
๐ฌ ๋ฌธ์ ์ค๋ช ์ฃผ์ด์ง `N`๊ฐ์ ์ขํ๊ฐ์ ๋ํด ์ขํ ์์ถ์ ์ํํ๋ ๋ฌธ์ ๋ก์ขํ ์์ถ์ด๋ ์๋ ๊ฐ์ ์๋์ ์ธ ํฌ๊ธฐ ์์๋ฅผ ์ ์งํ๋ฉด์ ๊ฐ๋ค์ 0๋ถํฐ ์์ํ๋ ์ฐ์๋ ์ ์๋ก ๋งคํํ๋ ๊ฒ์ ์๋ฏธํ๋ค. ๐ ์ฃผ์ ์ฌํญ๋จ์ ๊ตฌํ ์ ์๊ฐ ์ด๊ณผ ๋ฐ์`List.indexOf()` ๊ฐ์ ๋ฉ์๋๋ ๋งค๋ฒ `O(N)` ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ฏ๋ก ์ ์ฒด๊ฐ `O(N²)`์ด ๋์ด ์๊ฐ ์ด๊ณผ ๋ฐ์๋ฐ๋ผ์ ์ ๋ ฌ + ๋งต(Map) ์๋ฃ๊ตฌ์กฐ๋ฅผ ํ์ฉํด `O(N log N)` ์์ ํด๊ฒฐํด์ผ ํจ์ ๋ ฅ ํฌ๊ธฐ๊ฐ ํฌ๋ฏ๋ก `Scanner` ๋์ `BufferedReader` ๋๋ ์ปค์คํ ์ ๋ ฅ ํด๋์ค๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ข์ ๐ ๋ฌธ์ ํ์ด์ ๋ ฅ๋ฐ๊ธฐ๋ฐฐ์ด `nums`์ ์๋ณธ ์ขํ๊ฐ์ ์ ์ฅ์ ๋ ฌ ๋ณต์ฌ๋ณธ ๋ง๋ค๊ธฐ`nums`๋ฅผ ๋ณต์ฌํด์ `copy` ๋ฐฐ์ด์ ๋ง๋ ํ ์ ๋ ฌ์ขํ ์์ถ ๋งคํ ..
2025.09.04 -
[BOJ] 1715 - ์นด๋ ์ ๋ ฌํ๊ธฐ
๐ฌ ๋ฌธ์ ์ค๋ช ์ซ์๊ฐ ์ ํ ์นด๋ ๋ฌถ์์ด `N`๊ฐ ์๋ค. ์นด๋ ๋ฌถ์ ๋ ๊ฐ๋ฅผ ํฉ์น๋ฉด ๋ ๋ฌถ์์ ๋ค์ด ์๋ ์นด๋ ์์ ํฉ๋งํผ ๋น๊ต ํ์๊ฐ ๋ฐ์ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์๋ก ํฉ์ณ์ง ๋ฌถ์์ ๋ค์ ์นด๋ ๋๋ฏธ์ ๋ค์ด๊ฐ๋ค.๋ชจ๋ ์นด๋๋ฅผ ํ๋์ ๋ฌถ์์ผ๋ก ํฉ์น ๋ ํ์ํ ๋น๊ต ํ์์ ์ต์๊ฐ์ ๊ตฌํ๋ผ. ๐ ์ฃผ์ ์ฌํญ์นด๋ ๋ฌถ์์ ํฉ์น ๋๋ง๋ค ๊ทธ ํฉ์ด ๋น์ฉ์ผ๋ก ๋ํด์ง๋ค.์ค๊ฐ์ ํฉ์ณ์ง ๋ฌถ์๋ ๋ค์ ๋ค์ ์ฐ์ฐ์ ์ฐธ์ฌํด์ผ ํ๋ค.๋ฐ๋ผ์ ํญ์ ๊ฐ์ฅ ์์ ๋ ๋ฌถ์์ ๋จผ์ ํฉ์น๋ ์ ๋ต์ด ์ต์ ์ด๋ค.ํฐ ๋ฌถ์์ ๋จผ์ ํฉ์น๋ฉด ์ดํ ๋น์ฉ์ด ๋ ์ปค์ง๋ค.์ด ๋ฌธ์ ๋ ์ ํ์ ์ธ ๊ทธ๋ฆฌ๋ + ์ฐ์ ์์ ํ(์ต์ ํ) ๋ฌธ์ ๋ค. ๐ ๋ฌธ์ ํ์ด๋ชจ๋ ์นด๋ ๋ฌถ์์ ์ฐ์ ์์ ํ์ ์ฝ์ ํ๋ค.ํ์ ์์๊ฐ ๋ ๊ฐ ์ด์์ผ ๋์ ๋ฐ๋ณต:๊ฐ์ฅ ์์ ์นด๋ ๋ฌถ์ ๋ ๊ฐ๋ฅผ ๊บผ๋ธ๋ค.ํฉ์ณ์ ๋น์ฉ์ ๋..
2025.09.02 -
[BOJ] 2785 - ์ฒด์ธ
๐ฌ ๋ฌธ์ ์ค๋ช ์ฒด์ธ์ด `N`๊ฐ ์๋ค. ๊ฐ ์ฒด์ธ์ ์ฌ๋ฌ ๊ฐ์ ๊ณ ๋ฆฌ๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ ๊ณ ๋ฆฌ์ ๊ฐ์๊ฐ ๊ณง ์ฒด์ธ์ ๊ธธ์ด๋ค.์ฒด์ธ ๋ ๊ฐ๋ฅผ ์ฐ๊ฒฐํ๋ ค๋ฉด ํ ์ฒด์ธ์ ๊ณ ๋ฆฌ๋ฅผ ํ๋ ์๋ผ์ ๋ค๋ฅธ ์ฒด์ธ์ ์ด์ด์ผ ํ๋ค. ์ฆ ์ฐ๊ฒฐํ ๋๋ง๋ค ์ฒด์ธ ์๋ 1 ์ค์ด๋ค๊ณ ๋์์ ์ฌ์ฉํ ์ฒด์ธ์ ๊ธธ์ด๊ฐ 1 ์ค์ด๋ ๋ค.๋ชฉํ๋ ๋ชจ๋ ์ฒด์ธ์ ํ๋๋ก ์ฐ๊ฒฐํ๋ ๊ฒ์ด๋ค. ์ด๋ ํ์ํ ์ต์ ์ฐ๊ฒฐ ํ์๋ฅผ ๊ตฌํ๋ผ. ๐ ์ฃผ์ ์ฌํญ์ฐ๊ฒฐ ํ์์ ์ํ์ ํญ์ `N-1`์ด๋ค.์ฒด์ธ `N`๊ฐ๋ฅผ ํ๋๋ก ํฉ์น๋ ค๋ฉด ์ต์ํ `N-1`๋ฒ์ ์ฐ๊ฒฐํด์ผ ํ๋ค.ํ์ง๋ง ๊ฐ ์ฒด์ธ์ ๊ธธ์ด๊ฐ ์งง์ผ๋ฉด ๊ณ ๋ฆฌ๊ฐ ๋นจ๋ฆฌ ์๋ชจ๋ผ์ ์ค๊ฐ์ ๋ฉ์ถ ์ ์๋ค.๋ฐ๋ผ์ ์ค์ ์ฐ๊ฒฐ ํ์๋ ์ฒด์ธ์ ๊ธธ์ด ๋ถํฌ์ ๋ฐ๋ผ ์ค์ด๋ค ์๋ ์๋ค.๋ฌธ์ ์ ํต์ฌ์ ์ฒด์ธ ๊ธธ์ด๋ฅผ ๊ณ ๋ คํ์ฌ ์ต์ ํ์๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๋ค. ๐ ๋ฌธ์ ํ์ดํต์ฌ ์..
2025.08.31 -
[BOJ] 2831 - ๋์ค ํํฐ
๐ฌ ๋ฌธ์ ์ค๋ช `N`๋ช ์ ๋จ์์ `N`๋ช ์ ์ฌ์๊ฐ ์๋ค. ๊ฐ ์ฌ๋์ ์์ ์ ํค(์ ๋๊ฐ)์ ์ํ๋ ์กฐ๊ฑด(๋ถํธ)์ผ๋ก ํํ๋๋ค.- ์์ : ์์ ๋ณด๋ค ํค๊ฐ ํฐ ์ด์ฑ์ ์ํ๋ค.- ์์ : ์์ ๋ณด๋ค ํค๊ฐ ์์ ์ด์ฑ์ ์ํ๋ค. ์ด๋ ๊ฐ๋ฅํ ์ต๋ํ ๋ง์ ์ปคํ์ ๋งค์นญํด์ผ ํ๋ค. ๐ ์ฃผ์ ์ฌํญ๋ถํธ์ ์๋ฏธ๋ฅผ ํท๊ฐ๋ฆฌ๋ฉด ์ ๋๋ค.+ : ํฐ ์ฌ๋ ์ํจ (`~Up`)- : ์์ ์ฌ๋ ์ํจ (`~Down`)๋งค์นญ ์กฐ๊ฑด์ ๋ ๊ฐ์ง๋ฐ์ ์๋ค.๋จ์ Up ↔ ์ฌ์ Down, ์กฐ๊ฑด boy ๋จ์ Down ↔ ์ฌ์ Up, ์กฐ๊ฑด boy > girl์กฐ๊ฑด์ด ๋ฑ ๋ง์์ผ ๋งค์นญ ๊ฐ๋ฅํ๋ค.์ต๋ ๋งค์นญ ์๋ฅผ ๊ตฌํ๋ ๊ฒ์ด ๋ชฉํ๋ค. ๐ ๋ฌธ์ ํ์ด์ ๋ ฅ ๋ถ๋ฅ๋จ์/์ฌ์๋ฅผ ๊ฐ๊ฐ wantUp / wantDown ๋ ๊ทธ๋ฃน์ผ๋ก ๋๋๋ค.`abs(height)`๋ฅผ ์ ์ฅํด์ ์ค์ ..
2025.08.31 -
[BOJ] 2885 - ์ด์ฝ๋ฆฟ ์์ฌ
๐ฌ ๋ฌธ์ ์ค๋ช ๋น์ ์ ์ด์ฝ๋ฆฟ์ ๋จน์ผ๋ ค ํ๋ค. ์ด์ฝ๋ฆฟ์ ํญ์ ํ ๋ณ์ ๊ธธ์ด๊ฐ 2์ ๊ฑฐ๋ญ์ ๊ณฑ์ธ ์ ์ฌ๊ฐํ ๋ชจ์์ด๊ณ ๊ฐ์ด๋ฐ๋ก๋ง ์ชผ๊ฐ์ ๋ ๊ฐ๋ก ๋๋ ์ ์๋ค.์ด์ฝ๋ฆฟ์ ์ต์ ๋ช ๋ฒ ์ชผ๊ฐ์ผ ์ ํํ `K`์นธ์ ๋จน์ ์ ์์์ง ํ์ํ ์ต์ ์ด์ฝ๋ฆฟ ํฌ๊ธฐ์ ์ต์ ์ชผ๊ฐ๊ธฐ ํ์๋ฅผ ์ถ๋ ฅํ๋ค. ๐ ์ฃผ์ ์ฌํญ์ด์ฝ๋ฆฟ ํฌ๊ธฐ๋ ๋ฌด์กฐ๊ฑด 2์ ๊ฑฐ๋ญ์ ๊ณฑ์ด์ด์ผ ํจ์ชผ๊ฐค ๋๋ ๋ฐ์ผ๋ก๋ง ์ชผ๊ฐค ์ ์์์ชผ๊ฐ ์กฐ๊ฐ์ ๋ฐ๋ก ๋จน์ ์๋ ์๊ณ ๋ ํ์ํ๋ฉด ๊ณ์ ์ชผ๊ฐ๋ ๋จ์ชผ๊ฐ๋ ํ์๋ฅผ ์ต์ํํ๋ ๊ฒ ๋ชฉํ ๐ ๋ฌธ์ ํ์ด์ด์ฝ๋ฆฟ ํฌ๊ธฐ ์ ํ๊ธฐ์ ๋ ฅ `K` ์ด์์ธ ๊ฐ์ฅ ์์ 2์ ๊ฑฐ๋ญ์ ๊ณฑ์ ์ฐพ๋๋ค.→ ์ด ๊ฐ์ด ๊ณง ์ด์ฝ๋ฆฟ์ ์ต์ ํฌ๊ธฐ์ชผ๊ฐ๊ธฐ ๊ณผ์ (๊ทธ๋ฆฌ๋)`piece` = ์ด์ฝ๋ฆฟ ํฌ๊ธฐ, `rem` = `K` (๋จ์ ํ์ํ ์นธ)`while rem > 0`:๋ง์ฝ `piece..
2025.08.30 -
[BOJ] 17135 – ์บ์ฌ ๋ํ์ค
๐ฌ ๋ฌธ์ ์ค๋ช ์ฑ ๋ฐ๋ก ์๋์ 3๋ช ์ ๊ถ์๋ฅผ ๋ฐฐ์นํ๊ณ ๋ชจ๋ ์ ์ ์ ๊ฑฐํ๋ ๊ฒ์์ ์๋ฎฌ๋ ์ด์ ํ๋ ๋ฌธ์ ๋ก ๊ท์น์ ๋ค์๊ณผ ๊ฐ๋ค:1. ๋งค ํด ๊ฐ ๊ถ์๋ ๊ฐ์ฅ ๊ฐ๊น์ด ์ ํ๋๋ฅผ ๊ณต๊ฒฉํ๋ค. - ๊ฑฐ๋ฆฌ๋ ๋งจํดํผ ๊ฑฐ๋ฆฌ๋ก ๊ณ์ฐ - ๊ฐ์ฅ ๊ฐ๊น์ด ์ ์ด ์ฌ๋ฌ ๋ช ์ด๋ฉด ๊ฐ์ฅ ์ผ์ชฝ(์ด์ด ์์) ์ ์ ์ฐ์ ํ๋ค.2. 3๋ช ์ ๊ถ์๊ฐ ๋์์ ๊ณต๊ฒฉ์ ์ํํ๋ค. (๊ฐ์ ์ ์ ๊ฒจ๋ฅํด๋ ํ ๋ฒ๋ง ์ ๊ฑฐ๋จ)3. ๊ณต๊ฒฉ์ด ๋๋๋ฉด ์ ์ด ํ ์นธ ์๋๋ก ์ด๋ํ๋ค.4. ๋ชจ๋ ์ ์ด ์ฌ๋ผ์ง ๋๊น์ง ๋ฐ๋ณตํ๋ฉฐ ์ ๊ฑฐํ ์ ์ ์ต๋ ์๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค. ๐ ์ฃผ์ ์ฌํญํ๊น ์ ์ : “๊ฑฐ๋ฆฌ → ์ผ์ชฝ ์ฐ์ ” ๊ท์น์ ๋ฐ๋์ ๊ตฌํํด์ผ ํจ๋์ ๊ณต๊ฒฉ ์ฒ๋ฆฌ: ๊ฐ ๊ถ์๊ฐ ๊ณ ๋ฅธ ์ ์ ํ ๋ฒ์ ์ ๊ฑฐํด์ผ ํจ์ ์ด๋: ๋ผ์ด๋๋ง๋ค ๋งต์ ํ ์นธ ์๋๋ก ์ด๋์ํค๋ ๊ณผ์ ์ด ํ์๊ถ์ ๋ฐฐ์น: ..
2025.08.17