[백준] B17298 오큰수

문제

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

풀이

i번째 수가 입력된 시점에서 i번째 수에 대해 고려해야 할 것은 i번째 수를 오큰수로 가질 수들이다.
이들은 i번째 이전에 입력된 수들이다.

A0~An까지 입력할 때,

1. Ai 요소 입력 시,
   A0~Ai-1까지 중 아직 오큰수를 찾지 못한 요소들과 비교해야 한다.
   오큰수를 찾지 못한 요소들을 담아놓는 공간을 not_found_list, not_found_list에 가장 최근에 추가된 요소의 인덱스를 가리키는 값을 top이라고 하자.
   not_found_list에서 Ai보다 작은 요소들은 Ai를 오큰수로 할당해주고 not_found_list에서 지워준다.
   이후 Ai를 not_found_list에 추가해준다.

2. Ai는 not_found_list에 최근에 추가된 순서대로 비교를 진행한다.

   • Ai>Atop ? NGE(top)=Ai 할당 후 다음 top과 비교 진행
   • Ai<=Atop ? 비교 중단

   Ai-1보다 작은 요소들은 Ai-1번 요소 입력 당시에 위와 같은 과정을 통해 모두 판별되어 Ai-1를 오큰수로 가지게 되며 해당 로직 진행 시에 누락이 생기지 않는다.

LIFO 형식이므로 스택을 사용해준다.

코드

class NGES {
private:
	vector<int> nge;
	vector<int> input;
	int n;

public:
	NGES(int n) {
		this->n = n;
		nge.resize(n, -1); //초기화
	}

	void print() {
		for (int i = 0;i < n;i++) {
			cout << nge[i] << " ";
		}
		cout << endl;
	}

	void push() {
		stack<int> s; //오큰수 할당 안 된 인덱스 저장 스택

		for (int i = 0;i < n;i++) {
			int value;
			cin >> value;
			//현재 들어온 값과 아직 오큰수를 찾지 못한 인덱스들을 비교
			while(!s.empty()) {
				if (value <= input[s.top()]) break;
				nge[s.top()] = value;
				s.pop();
			}
			input.push_back(value);
			s.push(i);
		}
		print();
	}
};

int main() {
	int n;
	cin >> n; //수열의 크기

	NGES NGE(n);
	NGE.push();

	return 0;
}