-
[Algo Rhythm๐บ๐] ํ๋ก๊ทธ๋๋จธ์ค - ์ซ์ ๊ฒ์Algo Rhythm๐บ๐/Programmers 2022. 9. 24. 00:59
๐ซ๋ฌธ์ ๋ถ์
A ํ์๋ค์ด ๋ถ์ฌ๋ฐ์ ์๊ฐ ์ถ์ ์์๋๋ก ๋์ด๋์ด์๋ ๋ฐฐ์ด์ $A$, i๋ฒ์งธ ์์๊ฐ Bํ์ i๋ฒ ํ์์ด ๋ถ์ฌ๋ฐ์ ์๋ฅผ ์๋ฏธํ๋ ๋ฐฐ์ด์ $B$๋ผ๊ณ ํ์.
์ด๋ ๋ ๋ฐฐ์ด์ ์์ $a_i, b_i$, ๋ฐฐ์ด์ ํฌ๊ธฐ $L$์ ์๋์ ๊ฐ์ด ์ ์ํ ์ ์๋ค.
$1 \le L = \left\vert A \right\vert = \left\vert B \right\vert \le 10^5$
$1 \le a_i, b_i \le 10^9 (a_i \in A, b_i \in B, i \in \left[ 1, L \right])$
Aํ์ ์ถ์ ์์๊ฐ ์ด๋ฏธ ๊ณ ์ ๋์ด ์๋ค. ๋ฐ๋ผ์ Bํ์ด ์ต๋ ์น์ ์ ์ป๊ธฐ ์ํด์๋ ๊ฐ $a_i$๋ฅผ ํจ๋ฐฐํ ์ ์๋ ์ฆ, $a_i < b_i$ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ฐ์ฅ ์์ $b_i$์ ๋งค์นญํ๋ฉด ๋๋ค.
๐ฅ๋ฌธ์ ํ์ด
์์ ๋ถ์์์ ์ธ๊ธํ๋ฏ์ด ์ฐ๋ฆฌ๋ ๊ฐ $a_i$๋ฅผ $a_i \lt b_i$๋ฅผ ๋ง์กฑํ๋ ๊ฐ์ฅ ์์ $b_i$์ ๋งค์นญํด์ผ ํ๋ค.
๊ฐ์ฅ ๊ฐ๋จํ๊ฒ ๋ชจ๋ $b_i$๋ฅผ ์ผ์ผ์ด ์ดํด๋ณด๋ ๋ฐฉ๋ฒ๋ ๊ฐ๋ฅํ๋ค. ํ์ง๋ง $B$๋ฅผ ์ ๋ ฌํ ๋ค binary search๋ฅผ ์ด์ฉํ๋ฉด ๋ ๋น ๋ฅด๊ฒ ๋งค์นญํ ์ ์๋ค.
์ ๋ฆฌํ๋ฉด ์ด ๋ฌธ์ ๋ ๋ค์๊ณผ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํด๊ฒฐ๊ฐ๋ฅํ๋ค.
- $B$๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ
- ๋ชจ๋ $a_i$์ ๋ํ์ฌ ๋ค์ ๊ณผ์ ์คํ
- binary search๋ฅผ ํตํด $a_i \lt b_i$๋ฅผ ๋ง์กฑํ๋ ๊ฐ์ฅ ์์ $b_i$ ์ฐพ๊ธฐ
- ์ฐพ์ผ๋ฉด ์น์ ์ 1์ ์ ์ถ๊ฐํ๊ณ ํด๋น $b_i$๋ฅผ ๋ค์ ๊ณผ์ ์์ ์ ์ธ
โจ๋ณต์ก๋ ๋ถ์
๋ ๋ฐฐ์ด $A, B$์ ํฌ๊ธฐ๋ฅผ $n$์ด๋ผ๊ณ ํ์.
โฐ์๊ฐ ๋ณต์ก๋ : $O(n\log n)$
- $B$ ์ ๋ ฌ : $O(n \log n)$
- ๋ชจ๋ $a_i$์ ๋ํ์ฌ binary search๋ก $a_i \lt b_i$๋ฅผ ๋ง์กฑํ๋ ๊ฐ์ฅ ์์ $b_i$ ์ฐพ๊ธฐ : $O(n \log n)$
๐ ๊ณต๊ฐ ๋ณต์ก๋ : $O(n)$
๐์ฝ๋
๐๋ฌธ์ ์ถ์ฒ
https://school.programmers.co.kr/learn/courses/30/lessons/12987
'Algo Rhythm๐บ๐ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ