[백준] 17298 오큰수

1

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
	//입출력 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	vector <int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	
	for (int i = 0; i < n; i++) {
		bool check = true;
		for (int j = i + 1; j < n; j++) {
			if (v[i] < v[j]) {
				cout << v[j]<<" ";
				check = false;  break;
			}
		}
		if (check)
			cout << "-1 ";
	}

	return 0;
}

vector로 입력 받고 for문 두번 돌면서 검사 => 시간초과 

& vector에 받으면서 오른쪽 큰 수를 검사하기 빡셈

 

 

 

2

#include <iostream>
#include <queue>
using namespace std;

int main() {
	//입출력 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	queue <int> q;
    queue <int> temp_q;
    
    //q에 입력 받음 
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		q.push(a);
	}
	
    //하나씩 pop하면서 왼쪽 check 해당 수보다 큰 수있으면 out 
	while (n--) {
		int a_i = q.front(); q.pop();
		temp_q = q;
		while (!temp_q.empty() and a_i >= temp_q.front()) {
				temp_q.pop();
		}
		if (temp_q.empty())
			cout << "-1 ";
		else
			cout << temp_q.front()<<" ";
	}
	return 0;
}

 

=> 시간초과 

=>> queue 에  입력받으면서 check하는 쪽으로 

=>>>>>> queue로 입력받으면 안됨. q의 front로 검사하면 첫 입력부터 제일 큰 수가 들어오는 경우 나머지 모든 수들이 검사 안됨. q의 back으로 검사한다 치면 ? 출력을 순서대로 하기 어려울듯 ? 

 

 

3

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
	//입출력 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	stack <int> s;
	vector <int> v_in(n);
	vector <int> v_out(n,-1);

	//stack에 값을 저장하면 출력 벡터에 접근할때 인덱스에 대한 정보가 없음 
	//순회하기 어려운 stack에는 인덱스값만 저장해서 오큰수의 인덱스를 찾고 
	//벡터에 인덱스와 값을 동시 저장해서 벡터 접근으로 값을 알아내는 방법 

	for (int i = 0; i < n;i++) {
		int a; cin >> a;
		while (!s.empty() && v_in[s.top()] < a) {
			v_out[s.top()] = a;
			s.pop();
		}
		s.push(i);
		v_in[i] = a;
	}
	for (int i = 0; i < n; i++) {
		cout << v_out[i] << " ";
	}

	
	return 0;
}

stack + vector 사용해서 성공 

 

 

4

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
	//입출력 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n; cin >> n;
	stack <pair<int,int>> s;
	vector <int> v(n,-1);

	//vector 두개 사용하던거 stack에 pair로 인덱스,값으로 저장하면서 하나만 사용 
	for (int i = 0; i < n;i++) {
		int a; cin >> a;
		while (!s.empty() && s.top().second < a) {
			v[s.top().first] = a;
			s.pop();
		}
		s.push(make_pair(i,a));
	}
	for (int i = 0; i < n; i++) {
		cout << v[i] << " ";
	}
	return 0;
}

 

 

결과 :

 

4

 

3

 

메모리, 시간 ↓