백준 [boj 17298] 오큰수 C++ - 런타임 에러 (Segfault)

 

백만년만에 푸는 알고리즘

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

17298번: 오큰수

힌트: 스택의 경우 가장 최근의 것들을 저장히고 필요없거나 사용하면 버린다.

힌트 2: 예제 2번의 경우에  스택을 저장 한 후에  

 

틀린 이유1: 런타임 에러 (Segfault) 

nge[s.top()]을 할 때 비어있는 값이라고 인식 후 넘어가는 값이 아니라 쓰레기 값이 들어가 버린다.

 

틀린 이유2: 런타임 에러 (Segfault)

while ((!s.empty() && nge[s.top()] < nge[idx])) 에서 조건문 순서를 바꿔서

while (  nge[s.top()] < nge[idx])  && (!s.empty() ) 라고 해버리면 순서대로 검사 하기 때문에 또 잘 못된 메모리에 접근 한다. 

 

정답 코드:

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

const int MAX = 1000000 + 1;
stack <int> s;
int nge[MAX + 5];
int N;


int main() {
	
	cin >> N;
	int next;
	
	for (int idx = 0; idx < N ; idx++) {
		cin >> nge[idx];
		if (s.empty() || nge[s.top()] > nge[idx])
			s.push(idx);

		else  {
			while ((!s.empty() && nge[s.top()] < nge[idx])) {
				nge[s.top()] = nge[idx];
				s.pop();
			}
			s.push(idx);
		}
	}// 초기 스택

	while (!s.empty()) {
		nge[s.top()] = -1;
		s.pop();
	}

	for (int i = 0; i < N; i++) {
		cout << nge[i] << " ";
	}

	return 0;
}