#17298: 오큰수

백준 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)이 주어진다.

풀이:

우선 처음으로 이 문제를 풀 때 그냥 배열에 넣고 이중 for문 돌려서 하나씩 자신보다 큰 수 나올 때까지 확인하면 되는 것이 아닌가 생각하였지만 그래도 자료구조를 이용하여 풀어야 하는 문제니가 스택을 이용해 풀어보자라고 생각하고 풀었다.

이 문제는 스택을 총 3개 이용한다.

1. 처음 입력을 받는 스택 - s
2. 비교를 위한 스택 - NGE / 현재 확인 중인 스택의 오른쪽 스택을 저장 해 놓는 스택
3. 정답을 저장하는 스택 - answer
   • 우선 그 숫자에 맞는 답을 찾을 때마다 s.pop()을 할 것이기 때문에 s가 empty 될 때까지 while문을 돌린다.
   • 그리고 NGE가 비었는지 안비었는지 확인 해준다. 왜냐하면 제일 오른쪽 숫자일 경우 오른쪽 숫자가 없기 때문에 NGE가 비어있을 것이다. 비어 있을 경우에는 오른쪽에 숫자가 없기 때문에 answer에 -1을 넣어주고 현재 확인 중인 숫자를 NGE에 넣어주면서 s에서는 빼준다.
   • 이제 NGE가 안비어있을 경우에는 두가지 경우가 있다. NGE 제일 위에 숫자(오른쪽에서 제일 가까운 숫자)가 현재 확인 중인 숫자보다 큰 경우와 작은 경우 두가지이다.
   • 만약에 큰 경우에는 answer에 그 숫자를 넣어주고 NGE에 현재 숫자를 넣어주며 s에서 빼준다.

   • 작은 경우에는 NGE top에 있는 숫자를 다음 숫자와 비교 할 수 있도록 pop/빼준다.

     ⭐나는 처음 여기서 NGE top값을 빼주면 나중에 필요할 수도 있지 않을까 라는 생각을 하였다. 하지만, 빼줘도 문제가 없는 이유는 현재 비교중인 숫자가 NGE top 값보다 크고 비교를 할 경우 더 왼쪽에 있으므로 먼저 비교를 당할 것이다 . 현재 숫자가 답에 채택이 안되면 어짜피 우리가 빼버린 NGE top은 현재 숫자보다 작기 때문에 당연히 답이 될 수가 없다.

🔎문제를 다 풀고 이중 for문으로 문제를 풀어보았는데 38%쯤에서 시간 초과라고 나왔다. 이렇게 푼 사람이 있을 것 같아서 “질문 검색”탭에서 찾아보니 이렇게 풀면 시간 복잡도가 O(N^2)이 나와서 틀린다고 한다. 그에 비하면 스택으로 푼 답은 시간 복잡도가 O(N)이였다. N이 최대 1,000,000까지니까 제곱이 되고 안되고 차이가 큰 것 같다.

코드 결과 비교

제출 형식	결과	메모리(KB)	시간(ms)
스택 미사용	시간 초과
스택 사용	맞았습니다!	9012	604

코드(스택 사용):

#include <iostream>
#include <stack>

using namespace std;

int main(){
	int n;
	stack<int> s, NGE, answer;
	//입력
	cin >> n;
	for(int i = 0; i < n; i++){
		int temp;
		cin >> temp;
		s.push(temp);
	}

	while(!s.empty()){
		//제일 오른쪽 숫자가 아닐 때 
		if(!NGE.empty()){
			//오른쪽 숫자가 클 때 
			if(s.top() < NGE.top()){
				answer.push(NGE.top());
				NGE.push(s.top());
				s.pop(); 
			}
			//오른쪽 숫자가 작을 때 
			else{
				NGE.pop();
			}
		}
		//제일 오른쪽 숫자여서 NGE가 비어있을 때
		else{
			answer.push(-1);
			NGE.push(s.top());
			s.pop();
		}
	}
	//정답 출력
	for(int i = 0; i < n; i++){
		if(!answer.empty()){
			cout << answer.top() << " ";
			answer.pop();
		}
	}
}

코드(스택 미사용 - 시간 초과로 인한 오답 처리):

#include <iostream>

using namespace std;

int main(){
	int n;
	cin >> n;
	
	int numbers[n];
	for(int i = 0; i < n; i++) cin >> numbers[i];
	
	for(int i = 0; i < n; i++){
		if(i == n-1) cout << -1 <<" ";
		for(int j = i+1; j < n; j++){
			if(numbers[i] < numbers[j]){
				cout<<numbers[j]<<" ";
				break;
			}
			if(j == n-1) cout << -1 <<" ";
		}
	}
}