[G2] 백준 12015번 가장 긴 증가하는 부분 수열 2 C++ 이분 탐색, lower_bound

리뷰

 

lower_bound를 사용한 이분 탐색 문제 해당 문제를 풀이한다면 다른 문제 하나를 꽁으로 맞출 수 있다.

https://www.acmicpc.net/problem/12015

공짜 문제 리스트

1. [G2] 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.net/problem/12738
2. [S2] 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11722

 

문제 풀이

1. n값을 입력 받고, nums 배열에 수열의 정보를 입력 받는다, BS함수를 실행하고 해당 함수의 리턴값을 출력한다.
2. BS함수 실행 시 빈 벡터 temp를 초기화 해주고, nums 배열 내 n개의 수를 순회하며 탐색을 진행해 준다.
3. i번째 수 이상인 값이 temp내에 존재하는지 lower_bound 메서드를 통해 찾아 it에 저장해 준다.
4. it이 temp의 끝을 가르킨다면 nums[i] 이상의 값이 없으므로 temp의 뒤에 추가해 준다.
5. 아닐 경우 it에는 nums[i]이상인 메모리 주소가 담겨 있으므로 해당 값을 nums[i]로 교체해 준다.

 

참고 사항

lower_bound를 사용하여 O(logN)의 속도로 탐색을 하고 총 N개의 노드에 대한 탐색을 진행하여 총 O(NlogN)의 시간 복잡도로 문제를 풀 수 있다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int n, nums[1000000];

int BS() {
	vector<int> temp;
	for (int i = 0; i < n; i++) {
		auto it = lower_bound(temp.begin(), temp.end(), nums[i]);
		if (it == temp.end()) temp.push_back(nums[i]);
		else *it = nums[i];
	}
	return temp.size();
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> nums[i];
	cout << BS();
}