이것 저것 &

문제링크:https://www.acmicpc.net/problem/1756

구현문제로 분류되지만 그리디 알고리즘이라고도 생각할 수 있는 문제였습니다.

흔하게 생각하는 방법으로 구현하게 되면 

O(n*d) 의 시간복잡도가 걸리는 이준 포문을 구현할 수 있습니다.

하지만 해당 방법은 시간초과입니다. 

n,d 둘다 300000까지이기 때문입니다. 

그렇기 때문에 nlgn, n, d 만큼 걸리는 방법을 고안해야합니다.

n입장에서볼때 d배열에서 자신보다 작은위치 아래로는 들어갈 수 없습니다. 

즉, n => 3 2 5일 때 3은 d의 제일 아래인 3으로 갈 수 없습니다. 

그렇다면  5 6 4 3 6 2 3를 5 5 4 3 3 2 2 로 나타낼 수 있습니다. 어차피 작은 위치아래로는 내려갈 수 없기 때문이죠.

이렇게 배열을 바꾼 후에는 d 배열의 끝부터 n을 삽입할 수 있는지 순서대로 확인해주시면 됩니다. 

구현자체는 쉽고, 구현방법을 생각하는게 어려운 문제였습니다. 

정답코드입니다. 꼭 직접 작성해보세요! 화이팅 : ) 

#include <iostream>
using namespace std;
int d = 0, n = 0, result = 0;
int arr_d[300000] = { 0 };
int arr_n[300000] = { 0 };
int visited[300000] = { 0 };
int main() {
	cin >> d >> n;

	for (int i = 0; i < d; i++) {
		cin >> arr_d[i];
		if (i > 0 && arr_d[i - 1] < arr_d[i]) arr_d[i] = arr_d[i - 1];
	}
	for (int i = 0; i < n; i++)
		cin >> arr_n[i];



	int cnt = 0;
	for (int i = d - 1; i >= 0; i--) {
		if (arr_n[cnt] <= arr_d[i]) {
			visited[cnt] = 1 + i;
			cnt++;
		}
		if (cnt == n)
			break;
	}

	if (cnt == n)
		cout << visited[cnt - 1] << endl;
	else
		cout << 0 << endl;

	return 0;
}