2021. 12. 4. 00:03ใETC/Algorithm
์ด๋ถํ์ ๊ด๋ จ ๋ฌธ์ !
๋ฌธ์ ์ค๋ช
n๋ช ์ด ์ ๊ตญ์ฌ์ฌ๋ฅผ ์ํด ์ค์ ์์ ๊ธฐ๋ค๋ฆฌ๊ณ ์์ต๋๋ค. ๊ฐ ์ ๊ตญ์ฌ์ฌ๋์ ์๋ ์ฌ์ฌ๊ด๋ง๋ค ์ฌ์ฌํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๋ค๋ฆ ๋๋ค.
์ฒ์์ ๋ชจ๋ ์ฌ์ฌ๋๋ ๋น์ด์์ต๋๋ค. ํ ์ฌ์ฌ๋์์๋ ๋์์ ํ ๋ช ๋ง ์ฌ์ฌ๋ฅผ ํ ์ ์์ต๋๋ค. ๊ฐ์ฅ ์์ ์ ์๋ ์ฌ๋์ ๋น์ด ์๋ ์ฌ์ฌ๋๋ก ๊ฐ์ ์ฌ์ฌ๋ฅผ ๋ฐ์ ์ ์์ต๋๋ค. ํ์ง๋ง ๋ ๋นจ๋ฆฌ ๋๋๋ ์ฌ์ฌ๋๊ฐ ์์ผ๋ฉด ๊ธฐ๋ค๋ ธ๋ค๊ฐ ๊ทธ๊ณณ์ผ๋ก ๊ฐ์ ์ฌ์ฌ๋ฅผ ๋ฐ์ ์๋ ์์ต๋๋ค.
๋ชจ๋ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ต์๋ก ํ๊ณ ์ถ์ต๋๋ค.
์ ๊ตญ์ฌ์ฌ๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ์ฌ๋ ์ n, ๊ฐ ์ฌ์ฌ๊ด์ด ํ ๋ช ์ ์ฌ์ฌํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ๋ด๊ธด ๋ฐฐ์ด times๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ์ ๊ตญ์ฌ์ฌ๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ์ฌ๋์ 1๋ช ์ด์ 1,000,000,000๋ช ์ดํ์ ๋๋ค.
- ๊ฐ ์ฌ์ฌ๊ด์ด ํ ๋ช ์ ์ฌ์ฌํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ 1๋ถ ์ด์ 1,000,000,000๋ถ ์ดํ์ ๋๋ค.
- ์ฌ์ฌ๊ด์ 1๋ช ์ด์ 100,000๋ช ์ดํ์ ๋๋ค.
์ ์ถ๋ ฅ ์
n | times | return |
6 | [7, 10] | 28 |
๊ฐ์ฅ ์ฒซ ๋ ์ฌ๋์ ๋ฐ๋ก ์ฌ์ฌ๋ฅผ ๋ฐ์ผ๋ฌ ๊ฐ๋๋ค.
7๋ถ์ด ๋์์ ๋, ์ฒซ ๋ฒ์งธ ์ฌ์ฌ๋๊ฐ ๋น๊ณ 3๋ฒ์งธ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ์ต๋๋ค.
10๋ถ์ด ๋์์ ๋, ๋ ๋ฒ์งธ ์ฌ์ฌ๋๊ฐ ๋น๊ณ 4๋ฒ์งธ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ์ต๋๋ค.
14๋ถ์ด ๋์์ ๋, ์ฒซ ๋ฒ์งธ ์ฌ์ฌ๋๊ฐ ๋น๊ณ 5๋ฒ์งธ ์ฌ๋์ด ์ฌ์ฌ๋ฅผ ๋ฐ์ต๋๋ค.
20๋ถ์ด ๋์์ ๋, ๋ ๋ฒ์งธ ์ฌ์ฌ๋๊ฐ ๋น์ง๋ง 6๋ฒ์งธ ์ฌ๋์ด ๊ทธ๊ณณ์์ ์ฌ์ฌ๋ฅผ ๋ฐ์ง ์๊ณ 1๋ถ์ ๋ ๊ธฐ๋ค๋ฆฐ ํ์ ์ฒซ ๋ฒ์งธ ์ฌ์ฌ๋์์ ์ฌ์ฌ๋ฅผ ๋ฐ์ผ๋ฉด 28๋ถ์ ๋ชจ๋ ์ฌ๋์ ์ฌ์ฌ๊ฐ ๋๋ฉ๋๋ค.
๋ฌธ์ ํด๊ฒฐ
C++
#include <string>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
long long solution(int n, vector<int> times) {
sort(times.begin(), times.end());
ll low = 0, high = times.back() * n;
while (low != high) {
ll mid = (low + high) / 2;
ll pos = 0;
for (int t: times) pos += mid / t;
if (pos >= n) high = mid;
else low = mid + 1;
}
return low;
}
๊ฐ๋ฅํ ์๊ฐ์ ์ด๋ถ ํ์์ ํตํด ๊ตฌํฉ๋๋ค.
1) ์ฒ์ ๋ฒ์๋ [0, ๊ฐ์ฅ ์ค๋ ๊ฑธ๋ฆฌ๋ ์ฌ์ฌ ์๊ฐ * n] ์ผ๋ก ์ค์ ํฉ๋๋ค.
2) ๊ฐ๋ฅํ ์๊ฐ์ ํ์ํฉ๋๋ค.
2-1) mid ๊ฐ์ ๊ตฌํด mid ์๊ฐ ๋ด์ ๋ชจ๋ ์ฌ์ฌ๊ฐ ์งํ๋ ์ ์๋์ง ํ๋จํฉ๋๋ค.
2-2) ์ด๋, pos += mid / t ๋ ๊ฐ ์ฌ์ฌ๋ ๋ง๋ค ๋ฐ์ ์ฌ๋๋ค์ ํ๋จํฉ๋๋ค.
2-3) pos >= n , mid ์๊ฐ์ผ๋ก ๊ตฌํ ์์ฉ ์ธ์ (pos)์ด n๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค๋ฉด (๊ฐ๋ฅ์ฑ ์๋ ์ํ) ์กฐ๊ธ ๋ ์์ ๊ฐ์ผ๋ก ์๋ํฉ๋๋ค. (high = mid)
2-4) else, mid ์๊ฐ์ผ๋ก ๊ตฌํ ์์ฉ ์ธ์์ด n๋ช ๋ณด๋ค ๋ถ์กฑํ๋ค๋ฉด ๋ ํฐ ๊ฐ์ผ๋ก ์๋ํฉ๋๋ค.
'ETC > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Programmers, ์ง๊ฒ๋ค๋ฆฌ (2) | 2021.12.10 |
---|---|
Programmers, ๋ณดํ์ ์ฒ๊ตญ (2) | 2021.12.08 |
programmers, ๋จ์์นด๋ฉ๋ผ (0) | 2021.12.03 |
Programmers, ์ฌ ์ฐ๊ฒฐํ๊ธฐ (2) | 2021.12.02 |
Programmers, ๋จ์ฒด์ฌ์ง ์ฐ๊ธฐ (0) | 2021.12.02 |
Backend Software Engineer
๐๐ฎ๐ง ยท ๐๐ฎ๐๐ค๐ฃ๐๐จ๐ช๐ฃ ๐๐๐ง๐