주어진 배열에서 아래 조건을 만족하는 세개의 값이 존재하면 true리턴
i < j < k
and nums[i] < nums[j] < nums[k]
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> sub;
sub.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (sub[sub.size() - 1] < nums[i]) {
sub.push_back(nums[i]);
} else {
int j = 0;
while (sub[j] < nums[i]) j++;
sub[j] = nums[i];
}
if (sub.size() >= 3)
return true;
}
return false;
}
};
위의 풀이방법에서 sub 배열에서 값을 찾는것을 이진탐색하면 된다. sub배열은 값이 정렬된 배열이기 때문에 이진탐색이 가능하다.
class Solution {
public:
int binary_search(vector<int> &sub, int tgt) {
int left = 0;
int right = sub.size() - 1;
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (sub[mid] == tgt) {
return mid;
} else if (sub[mid] < tgt) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
bool increasingTriplet(vector<int>& nums) {
vector<int> sub;
sub.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (sub[sub.size() - 1] < nums[i]) {
sub.push_back(nums[i]);
} else {
// find position in sub[] with binary search
int pos = binary_search(sub, nums[i]);
sub[pos] = nums[i];
}
if (sub.size() >= 3)
return true;
}
return false;
}
};
우선 first, second변수를 최대값으로 초기화 하고, 배열을 순회하면서 이 변수를 가장 작은값, 그다음 작은값으로 업데이트 하는방식이다.
솔루션에서 배운 풀이방법인데, 대단히 간결하고 신박하다. 게다가 O(n) 시간복잡도를 갖는다. 같은 원리로 3개 뿐만아니라 고정된 k개의 increasing subsequence가 존재하는지 찾는 문제는 모두 이 방식으로 해결이 가능하다. 시간복잡도도 O(n).
[1,2,0,3] 의 경우
2st 값이 없데이트 되었다는 의미는, 이전에 1st값이 반드시 존재했었다는것을 의미 (이전 시점의 1st 값보다는 반드시 크다)
|
| * <---- 3st도 마찬가지, 따라서 지금까지의 2st보다 큰 값이 있다는건, 결국 1st 2st 3st 이렇게 점진적으로 증가하는 sub sequence가 존재한다는것을 의미
*
*
*
1 2 0 3
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int first = INT_MAX;
int second = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] <= first) // 기존에 업데이트한 first값보다 작은경우 재 업데이트.
first = nums[i];
else if (nums[i] <= second) // 자동으로 first보다 크면서 second보다 작거나같은 값을 다시 업데이트
second = nums[i];
else // second보다 큰값이 존재한다는것은 3번의 증가하는 subsequence가 있다는 의미.
return true;
}
return false;
}
};
아래는 pass가 되기전까지 시도해봤던 아이디어인데, 왜 오류가 났을지 생각해보자.
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> sub;
sub.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (sub[sub.size() - 1] < nums[i]) {
sub.push_back(nums[i]);
} else {
int j = 0;
while (sub[j] < nums[i]) j++;
sub[j] = nums[i];
}
if (sub.size() >= 3)
return true;
}
return false;
}
};
20 100 10 12 5 13 의 경우는 오답. 바로 직전 작은 값만 가리키기 때문.
/*
index 0 1 2 3 4 5
nums 1 5 0 4 1 3
index [2] [4] [5]
nums[i] 0 <- 1 <- 3
nr_link 3 2 1
*/
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int last_idx = nums.size() - 1;
stack<pair<int, int>> st; // contain <index, nums>
vector<int> nr_link(nums.size(), 1);
// increasing monotonic stack -> next small value
st.push(make_pair(last_idx, nums[last_idx]));
for (int i = last_idx - 1; i >= 0; i--) { // from the last to begin
int max_nr_link = 0;
int candidate_max = 0;
while (!st.empty() && nums[i] < st.top().second) {
pair<int, int> elem = st.top();
st.pop();
// find maximum number of linked
candidate_max = nr_link[i] + nr_link[elem.first];
max_nr_link = std::max(candidate_max, max_nr_link);
}
nr_link[i] = max_nr_link;
if (nr_link[i] >= 3)
return true;
st.push(make_pair(i, nums[i]));
}
return false;
}
};