์๋ ํ์ธ์ ์ฃผ์ธ์ฅ H์ ๋๋ค. ์ง๊ธ๊น์ง ์ ํ, ๋ฒ๋ธ, ์ฝ์ , ํต, ๋ณํฉ, ํ ์ ๋ ฌ์ ๊ฐ๋ ์ ๊ณต๋ถํด๋ณด์๊ณ , ๊ฐ์ฅ ๋นผ์ด ์ ๋ ฌ์ O(N * log N)์ด ๋์ค๋ ํต, ๋ณํฉ, ํ ์ ๋ ฌ ์ด์์ต๋๋ค. ํ์ง๋ง ์ด๋ณด๋ค ๋์ฑ ๋น ๋ฅธ ์ ๋ ฌ์ ์งํํด์ผ ํ๋ค๋ฉด ์ด๋ป๊ฒ ํด์ผํ ๊น์ ๋ค์์ 3 ์ดํ์ ๋ฐ์ดํฐ ์์ฐ์๋ค์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ฆฌํ์ธ์ 1 3 2 3 1 2 3 2 1 3 10๊ฐ์ ๋ฐ์ดํฐ๊ฐ ๋ชจ๋ 3์์ ์๋๊ฑธ ์ ์ ์๋๋ฐ์. ์ด์ฒ๋ผ ๋ฒ์์กฐ๊ฑด์ด ์๋ ๊ฒฝ์ฐ์ ํํด ๊ต์ฅํ ๋น ๋ฅธ ์๊ณ ๋ฆฌ์ฆ ์ ๋๋ค. ์๋๋ O(N)์ ๋๋ค. ๊ณ์์ ๋ ฌ์ ํฌ๊ธฐ๋ฅผ ๊ธฐ์ค์ผ๋ก ๊ฐฏ์๋ฅผ ์ธ๋ฉด ์ด๋จ๊น? ๋ ๋ฐ์์์ ์์ํฉ๋๋ค. ์ฆ ์ธ๊ฐ์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ 1์ด๋ฉด arr[0]++ 3์ด๋ฉด arr[2]++ ์ด๋ฐ์์ผ๋ก ์ซ์๋ฅผ ์ธ์ฃผ๋ฉด ๋ฉ๋๋ค. ๊ทธ๋ฌ๋ฉด ์ซ์์ ๊ฐฏ์๊ฐ ์ธ์งํ ๊ณ 1์ ar..