[백준] 17298번. 오큰수

leeeha·2022년 6월 25일

목록 보기

31/186

문제

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

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

풀이과정

시간 초과: O(n^2)

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

int main() {
	int n;
	cin >> n;

	vector<int> v;
	for(int i = 0; i < n; i++){
		int num;
		cin >> num;
		v.push_back(num);
	}

	vector<int> nge;

	for(int i = 0; i < n; i++){
		bool found = false;
		
		// i+1 인덱스부터 탐색 
		for(int j = i + 1; j < n; j++){
			// v[i]보다 크면서 인덱스가 가장 작은 수 저장  
			if(v[i] < v[j]){
				found = true;
				nge.push_back(v[j]);
				break;
			}
		}

		if(!found || i == n - 1){
			nge.push_back(-1);
		}
	}
	
	for(auto e: nge){
		cout << e << " ";
	}
	
	return 0;
}

🤔 다른 방법 생각해보기

https://cocoon1787.tistory.com/347

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

stack<int> s;
int ans[100'0001];
int arr[100'0001];

int main(){
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	// 오른쪽에서 왼쪽으로 이동 
	for (int i = n - 1; i >= 0; i--){
		while (!s.empty() && (s.top() <= arr[i])){
			s.pop();
		}

		if(s.empty()){
			ans[i] = -1; 
		}else{
			// s.top() > arr[i] 
			ans[i] = s.top(); // top 원소의 값을 저장 
		}

		// 스택의 bottom->top (내림차순)
		s.push(arr[i]); 
	}
	
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
}