๐ ๋ฌธ์
๐ฑ ์์ด๋์ด
์ค์ํ ์ ํ์ ๋ฌธ์ , ์ผ๋จ ๋ฌด์์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ ์ง ์๊ฐํด ๋ณด์
์ ๋ฌธ์ ์ ํต์ฌ์ ์ขํ์ ๋ฒ์ L์ด ์ฃผ์ด์ง ๋ end - start <= L์ด ๋ง์กฑํด์ผ ํ๋ค, ์ฆ ๊ตฌ๊ฐ๋ง๋ค L๋ฒ์์ ํด๋นํ๋
์ ๋ถ์ ๊ฐ์๋ฅผ ์ธ์ผ ํ๋ค.
์ขํ ๊ตฌ๊ฐ๋ง๋ค ์ ๋ถ์ด ํด๋นํ๋์ง ํ๋จํ๊ณ , ๋ฒ์์ฒดํฌ๊น์ง ํ๋ค๋ฉด ์์นซ O(N^2) ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๊ฒ ๊ตฌํํ ์ ์๋ค.
ํ์ง๋ง N์ ๋ฒ์๊ฐ 100,000๊น์ง ์ด๋ฉฐ O(N) ์ดํ๋ก ๊ตฌํํด์ผ ํ๋ค.
๋จผ์ ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฌํ๋ ๊ณผ์ ์ด ํ์ํ๋ค. y์ถ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๊ณ ํ์ชฝ ๋ฐฉํฅ์ผ๋ก ์ญ ์ค์บํ๋ฉด์ ๊ณ์ฐ์ ํ๋ฉด ๋๋ค
์ฆ ํ์ชฝ -> ๋ฐ๋์ชฝ์ผ๋ก ์ญ ์ค์บ์ ํ๋ ์ค์ํ ๋ฐฉ์์ผ๋ก ๊ตฌํํ๋ฉด O(N)์ ์๊ฐ๋ณต์ก๋๋ก ๋น ๋ฅด๊ฒ ๊ตฌํ ๊ฐ๋ฅํ๋ค.
์ ๋ ฌ ํ ๊ฐ์ฅ ์๋ (10, 20)๋ถํฐ last์ x๋ฅผ ๋ฃ๊ณ ๊ณ์ฐํ๋ค. 10 < 20 -L = false -> last๋ฅผ ๋น์ธํ์๊ฐ ์๋ค.
๋ฐ๋๋ก 5 < 40 -30 = true ์ผ ๋ ๋ฒ์๋ฅผ ๋ฒ์ด๋ฌ๊ธฐ ๋๋ฌธ์ last์์ 5๋ฅผ ์ ๊ฑฐํ๋ค
์ฆ ์ด๋ ๊ฒ ์งํํ๋ฉด์ last ํ์ ๊ฐ์ฅ ๋ง์ ์์๊ฐ ๋ด๊ฒผ์ ๋๊ฐ ๊ฐ์ฅ ๋ง์ด ๊ฒน์น๋ ๋ถ๋ถ์ด๊ณ , ์ถ๋ ฅํ๋ฉด ๋๋ค.
๐ฑ ์ฝ๋ ๋ฐ ํ์ด
๋งค๋ฒ last.size()๋ฅผ ๊ตฌํ๊ณ max๊ฐ์ ๊ตฌํ๋ฉด ๋๋ค!
๊ทธ๋ฆฌ๊ณ ์ ๋ถ x, y๋ ํ ์์ด๊ธฐ ๋๋ฌธ์ last.offer() ์ฐ์ฐ์ ์์ ํ๊ณ ๊ทธ ํ while๋ฌธ์์ ์กฐ๊ฑด์ ๋ฐ์ ธ์ผ ํ๋ค.
๐ฑ ๋๋ ์
์ด๋ ค์ ๋ ๋ฌธ์ ์๋ค, ์ ๋ ฌ์ ์ด๋ป๊ฒ ํด์ผ ํ๋์ง ๊ณ ๋ฏผํ๋ค ์๊ฐ์ ๋ง์ด ๋ณด๋๋ค, ์ค์ํ ์ ํ์ ๋ง์ด ์ ํ์ด๋ด์
์ต์ํ์ง ์์๋๋ฐ ์ด๋ ๊ฒ ์์ฉ๊ฐ๋ฅํ๋ค๋ ๊ฒ์ ๋ค์ ๋ฐฐ์๊ฐ๋ ๋ฌธ์ ์๋ค
'Algorithm > - Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 16496 ํฐ ์ ๋ง๋ค๊ธฐ (JAVA) (0) | 2024.05.23 |
---|---|
[BOJ] ๋ฐฑ์ค 17267 ์๋จ์ (JAVA) (0) | 2024.05.14 |
[BOJ] ๋ฐฑ์ค 1377 ๋ฒ๋ธ ์ํธ (JAVA) (1) | 2024.05.03 |
[BOJ] ๋ฐฑ์ค 31782 ์ ์ฒด์จ์ฆ (JAVA) (0) | 2024.04.30 |
[BOJ] ๋ฐฑ์ค 4195 ์น๊ตฌ ๋คํธ์ํฌ (JAVA) (1) | 2024.04.15 |
๋๋ง์ ๊ฐ๋ฐ ๋ฐ์ดํฐ๋ฒ ์ด์ค!
ํฌ์คํ ์ด ์ข์๋ค๋ฉด "์ข์์โค๏ธ" ๋๋ "๊ตฌ๋ ๐๐ป" ํด์ฃผ์ธ์!