user-img
์‰ฌ์šด ํ’€์ด 1
thumbnail
[๋ฐฑ์ค€] 2003 ์ˆ˜๋“ค์˜ ํ•ฉ2 ์‰ฌ์šด ํ’€์ด java ^^
1. ๋ฌธ์ œ ์„ค๋ช… ๐Ÿ“Œ๋ฌธ์ œ ๋งํฌ2. ์ ‘๊ทผ ๋ฐฉ์‹ ๐Ÿ—ƒ๏ธKEY WORD: one-way Two pointer๋‹จ๋ฐฉํ–ฅ ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์ „ํ˜•์ ์ธ ๋ฌธ์ œ์ด๋‹ค. ์™ผ์ชฝ ํฌ์ธํ„ฐ(L)๊ณผ ์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ(R)์„ ๋‘”๋‹ค. ํ•ด๋‹น ๊ตฌ๊ฐ„ ๋‚ด ์ˆ˜๋“ค์˜ ํ•ฉ์„ sum์ด๋ผ ํ•˜๊ฒ ๋‹ค.sum : R ํฌ์ธํ„ฐ๋ฅผ ์ „์ง„์‹œํ‚จ๋‹ค.sum >= M: L ํฌ์ธํ„ฐ๋ฅผ ์ „์ง„์‹œํ‚จ๋‹ค. (๋งŒ์•ฝ sum == M์ด๋ฉด ๋‹ต์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ +1 ์˜ฌ๋ฆฐ๋‹ค.)๊ตฌ๊ฐ„ ๋‚ด์˜ ํ•ฉ์€ ๊ตฌ๊ฐ„ ๋‚ด์˜ ๊ฐ’์ด ์›์†Œ ํ•˜๋‚˜์ธ ๊ฒฝ์šฐ๋„ ํฌํ•จํ•œ๋‹ค. ๋”ฐ๋ผ์„œ arr[0] == M ์ธ ๊ฒฝ์šฐ๋„ ์˜ˆ์™ธ ์—†์ด ๊ณ„์‚ฐ์— ํฌํ•จ๋˜๋„๋ก ํ•ด์ค˜์•ผ ํ•œ๋‹ค.๋‚˜๋Š” 3๋ฒˆ์˜ ๊ทœ์น™์„ ์ง€ํ‚ค๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์„ N+1๋กœ ๋งŒ๋“ค์–ด ๊ฐ’๋“ค์„ 1๋ถ€ํ„ฐ ์ฑ„์šฐ๊ณ , ํฌ์ธํ„ฐ๋“ค์€ 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋„๋ก ํ•˜์˜€๋‹ค.3. ์ฝ”๋“œ ์†Œ๊ฐœ ๐Ÿ”Žimport java.io.*;import java..
2024.12.23
์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฌธ์ œ ํ’€์ด