start_day인덱스부터 스트릭을 계산해 나가기 시작한다.- 주어진 p로 구할 수 있는 가장 큰 날짜
optimal_day를 구한다. with 이분탐색 :: last-true start_day..=optimal_day구간의 영어공부를 한 날과 추가로 체크할 수 있는 날p의 합이 곧start_day에서의 최적의 스트릭이다.
풀이#
삽질을 좀 했다. 파라메트릭 서치를 이용하는 것 까지는 파악했으나, 결정문제 안에서 O(N), O(N*N)의 시간을 사용하면 아무 의미가 없어져 버리는 것이었다!
sol1#
최대 20만개의 정수를 벡터에 넣기가 싫어서 메인함수에서 입력을 전역적으로 처리한 뒤에 solution을 호출하는 방향으로 계획했으나… 별로 좋은 생각이 아니었다.
-
이 문제는 길이 L짜리 스트릭을 생성할 수 있는지 에 관한 문제임이 틀림없다! ⇒ \(f(L)=True , False\)
-
길이 L짜리 Sliding Window를 사용하면 영어공부를 완료한 날들 사이 비어있는 칸의 수를 셀 수 있고, 한 번 훑었을 때 비어있는 칸의 수가
p이하이기만 하면 True를, 아니면 False를 통과시키기로 했다.-
Sliding Window를 구현하기 위해 필요한 건 영어공부를 완료한 날들을 훑기 위한 배열이었다. 하지만 최대 1,000,000개의 날짜를 단순 int형 배열에 담기엔 너무 많았고, bitset 을 직접 구현하는 것으로 최적화를 달성할 수 있었다.
-
custom
bitset총 10^6개의 비트, unsigned int 자료형이 32비트니까 총 31250개의 int형이 있으면 된다.
constexpr u32 MAX_DAY = 1'000'000; constexpr u32 MAX_N = 200'000; constexpr u32 MAX_P = 200'000; namespace bitset { constexpr u32 BITS = sizeof(u32) * 8; constexpr u32 MAX_BUCKETS = MAX_DAY / BITS; static array<u32, MAX_BUCKETS + 1> _bitset; inline void init() { _bitset.fill(0); } inline bool check(u32 idx) { auto bucket = idx / BITS; auto bit = idx % BITS; return (_bitset[bucket] >> bit) & 1; } /**set bit to true*/ inline void set(u32 idx) { auto bucket = idx / BITS; auto bit = idx % BITS; _bitset[bucket] |= (1 << bit); } /**set bit to false*/ inline void reset(u32 idx) { auto bucket = idx / BITS; auto bit = idx % BITS; _bitset[bucket] &= ~(1 << bit); // X & 0b111111011111 } } // namespace bitset
-
-
이 문제는 True → False 순서로 이루어져 있고, 가장 마지막 True를 찾으면 되는 문제이다.
- 가장 마지막 True는 가장 처음 False 를 찾은 뒤에 해당 인덱스 -1 하면 된다.
-
이분탐색 알고리즘의 정수가 바로 아래의 코드에 들어있다. 전략패턴을 사용하여 세부사항을 분리했다.
-
first_true,first_false/** @breif: False -- True 구간의 첫번째 True를 찾아줘요. @param: - begin: inclusive - end: exclusive - pred: predicate, 이를 사용하여 first_true도, first_false도 가능. */ template <typename T, class Predicate> inline T first_true(T begin, T end, Predicate const &pred) { auto l = begin; auto r = end; while (l != r) { auto m = l + (r - l) / 2; // overflow 방지 if (pred(m)) { // 구간 [m, r) 을 볼 필요 없으니 다음 구간은 [l, m)이다. r = m; } else { // 구간 [l, m + 1)를 볼 필요 없으니 다음 구간은 [m+1, r)이다. l = m + 1; } } return l; }/** @breif: True -- False 구간의 첫번째 False를 찾아줘요. */ template <typename T, class Predicate> inline T first_false(T begin, T end, Predicate const &pred) { auto pred_inversed = [&pred](auto i) { return !pred(i); }; return first_true(begin, end, pred_inversed); }
-
solution()sliding window가 앞으로 한 칸씩 움직일 때마다 윈도우 내부에 빈칸의 개수를 갱신해주어야 한다. 결과적으로 pred 람다함수가 0부터 N의 최대값까지 움직이기 때문에 최악 케이스 O(N)의 시간복잡도를 갖게 되었고, 이 pred 를 이분탐색 알고리즘이 호출하니까 전체적으로 보면 O(NlgN)이 되었다. 결과는? 시간초과.
inline int solution(u32 n, u32 p, u32 last_day) { // 길이 length 의 스트릭을 달성할 수 있나요? auto pred = [p, last_day](int length) { // window[0:length - 1] 안에 비어있는 check의 개수 int window = 0; for (int i = 0; i < length; ++i) { // init window window += bitset::check(i) ? 0 : 1; } // slide window for (int i = 1; i <= last_day - length; ++i) { if (window <= p) { return true; } window -= bitset::check(i - 1) ? 0 : 1; // left delete window += bitset::check(i + length - 1) ? 0 : 1; // right add } return false; }; return first_false<u32>(1, n + p, pred) - 1; }
sol2#
좀 더 효율적으로 수행하기 위해 영어공부한 날짜들 사이의 간격을 사용해보면 어떨까? 해서 solution 함수의 시그니처를 변경했다.
-
solution()이제 main함수에서 바로 bitset을 초기화 하지 않고 벡터를 만들어 참조를 전달하면 되어 편해졌다. 먼저 비트셋을 초기화 하고 델타 함수를 만들어 두 원소 간에 차를 저장하게 만들었다. 마찬가지로 이분탐색시, T/F를 구분할 predicate 함수를 제공하였으나, 이번엔 별도의 함수로 따로 뺐다.
inline int solution(vector<u32> const &days, u32 p) { bitset::init(); for (auto e : days) { bitset::set(e); } vector<u32> delta; for (size_t i = 0; i < days.size() - 1; ++i) { delta.emplace_back(days[i + 1] - days[i]); } return first_false<u32>( // 1, u32(days.size()) + p, [&delta, &p](auto length) { return _predicate(delta, p, length); }) - 1; } -
_predicate()지금 와서 생각해보면 솔루션에 가장 근접했던 코드였다. 다만 첫번째 for 문이 이분탐색 밖에 있었으면 좋았을 텐데… 결국 sol2는 중복된 작업을 여러번 반복하게 되었고, 결과적으로 시간초과가 발생하게 되었다.
어쨌든 첫번째 for문이 하는 일은 평가의 시작지점을 정한다. 이번엔 슬라이딩 윈도우를 사용하지 않고 델타의 각 원소들을 순회하며 그 사이에 p가 낑겨 들어갈 수 있는지 판단하고, 만약 가능하면 스트릭의 길이를 계산하여 참 거짓 여부를 조사하게 된다.
inline bool _predicate(vector<u32> const &delta, u32 p, int length) { if (p >= length - 1) { // 처음과 끝 return true; } // 중간 for (auto begin = delta.begin(); begin != delta.end(); ++begin) { int streak = 1; u32 sum = 0; // 구간의 공백의 개수 for (auto itr = begin; itr != delta.end(); ++itr) { auto const &elem = *itr; sum += elem - 1; if (sum > p) { break; } streak += elem; if (streak + (p - sum) >= length) { return true; } } } return false; }
sol3#
멘탈이 나가버렸다. 블로그 글을 검색해보기도 했는데 머리에 들어오는 것은 없었다. 일단 가장 근본적인 문제를 다시 생각해 보기로 했다.
start 번째 날짜부터 셀 수 있는 가장 긴 streak을 찾아라 ⇒ 이분탐색 with last-true
| days | 3 | 5 | 6 | 10 | 11 |
|---|---|---|---|---|---|
| blanks | 0 | 1 | 0 | 3 | 0 |
| blanks_cum | 0 | 1 | 1 | 4 | 4 |
start = 0일때 탐색 범위는 [0,5)이다.
- 주어진 p로 메꿀 수 있는 가장 큰 날짜(last-true)를 구한다
- 남은 p를 그 뒤에 붙여 스트릭 개수를 구한다.
수도코드로는 다음과 같다. streak 는 start ~ optimal_day 까지 수강한 영어수업의 개수와 그 사이에 비어있는 공백을 모두 메운 값이 된다.
for start in range(len(days)):
optimal_day = last_true(start, N)
streak = p
streak += optimal_day - (start - 1)
answer = max(answer, streak)
last_true() 는 다음과 같이 구현할 수 있겠다.
def last_true(start, N):
l = start
r = N
while l < r:
mid = l + (r - l) / 2
blank = blanks_cum[mid] - blanks_cum[start]
if (p < blank):
# cannot fill, move left range into [l, mid)
r = mid
else:
# can fill, move right range into [mid + 1, r)
l = mid + 1
return l - 1 # l 은 현재 first-false를 가리키고 있다. last-true는 바로 전 원소임
참고로 아래 `binary_search` 함수는 아예 날짜가 아니라 최대스트릭을 리턴하니 읽을때 주의하기 바란다.
```cpp
/**
@breif:
bitset을 사용하지 않는 이진검색
@param:
- days: 정렬된 상태를 보장하는 영어공부를 실시한 날짜들
- p: 추가적으로 영어공부를 했다고 뻥칠 수 있는 날들의 개수
*/
inline int solution(vector<u32> const &days, u32 p) {
// 0번째 날짜부터 i번째 날짜까지 공백의 개수
vector<u32> blanks;
std::adjacent_difference(days.begin(), days.end(), //
std::back_inserter(blanks),
[](auto a, auto b) { return a - b - 1; });
blanks[0] = 0; // 0번째 날짜는 세지 않는다.
std::partial_sum(blanks.begin(), blanks.end(), blanks.begin());
int max = 0;
// i번째 날짜부터 셀 수 있는 가장 긴 streak
for (size_t i = 0; i < days.size(); ++i) {
max = std::max(max, binary_search(blanks, i, p));
}
return max;
}
```
-
binary_search()/** @breif: start번째 날짜부터 시작했을 때 가능한 가장 긴 연속 구간의 길이를 찾자. @param: - blanks: 0번째부터 i번째 날짜까지 비어있는 칸의 개수 */ inline int binary_search(vector<u32> const &blanks, int start, u32 p) { auto l = start; auto r = int(blanks.size()); // exclusive // 주어진 p로 메꿀 수 있는 가장 큰 날짜번호를 구한다. -- last true while (l < r) { auto mid = l + (r - l) / 2; auto blank = blanks[mid] - blanks[start]; if (p < blank) { // go left, next range is [l, mid) r = mid; } else { // go right, next range is [mid + 1, r) l = mid + 1; } } // p를 포함하고 영어공부한 날짜의 개수도 포함한 결과가 스트릭이다. return p + (l - start); }
sol4#
sol3은 이분탐색을 별도로 구현했지만, 밥을 먹고 돌아와보니 이걸 처음에 만들었던 first-true, first-false 에 익명함수로도 사용할 수 있을 것 같았다. 그래서 더 간결하게 만든 소스코드이다.
-
solution()inline size_t solution(vector<u32> const &days, u32 p) { // 0번째 날짜부터 i번째 날짜까지 공백의 개수 vector<u32> blanks; std::adjacent_difference(days.begin(), days.end(), // std::back_inserter(blanks), [](auto a, auto b) { return a - b - 1; }); blanks[0] = 0; // 0번째 날짜는 세지 않는다. std::partial_sum(blanks.begin(), blanks.end(), blanks.begin()); size_t max = 0; for (size_t i = 0; i < days.size(); ++i) { // i번째 날짜부터 p로 다 채우지 못하는 첫번째 날짜 first-false auto upper_bound = first_true(i, days.size(), [&blanks, &i, &p](u32 day) { auto blank = blanks[day] - blanks[i]; return p < blank; }); // streak의 길이는 p를 포함하고 영어공부한 날도 포함이다. // 이때 영어공부한 날의 수는 시작한 날인 i부터 p로 채울 수 있는 // 마지막 날짜를 구한다. 따라서 p + (upper_bound - 1) - (i - 1) auto streak = p + (upper_bound - i); max = std::max(max, streak); } return max; }