백준 17298 c++ "오큰수" -PlusUltraCode-

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

 

 

 

[필자 사고]

현재 N의 크기가 1000000정도가 되면 시간복잡도 N^2으로는 풀리지 않는 문제이다.

 

처음 이 문제를 접하게 되면 스택을 이용하여 문제를 해결하는 아이디어가 쉽게 떠오르지 않을 것이다.

 

필자는 과거 유사한 문제를 풀어 본 경험이 있어 스택을 이용해 이 문제를 해결했따.

 

1. 스택이 비어있으면 현재 idx 를 스텍에 넣는다.

2. 스택의 맨 위의 idx의 실제 값과 비교하려는 값을 비교한다.

3. 스택의 맨 위값이 더 작으면 스택의 idx에 해당하는 배열에 비교하려는 큰 값을 넣는다.

4. 위 규칙이 어긋날때까지 반복 후 비교하려는 idx 를 스택에 저장한다.

 

[소스 코드]

 

#include <iostream>
#include<vector>
#include <stack>

using namespace std;

int N;

stack<int> stk;
vector<int> arr;
vector<int> resultVec;
void Input() {
	cin >> N;
	arr.resize(1000001);
	resultVec = arr;

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

void checkStackNum(int startIdx) {

	if (stk.empty()) {
		stk.push(startIdx);

		return;
	}

	int cmpIdx = startIdx;
	int cmpNumber = arr[cmpIdx];

	while (!stk.empty()) {
		int nowTopIdx = stk.top();
		int nowTopNumber = arr[nowTopIdx];

		if (nowTopNumber < cmpNumber) {
			stk.pop();
			resultVec[nowTopIdx] = cmpNumber;
			continue;
		}

		else {
			stk.push(cmpIdx);
			return;
		}
	}

	if (stk.empty()) {
		stk.push(cmpIdx);
		return;
	}

}


void GameStart() {

	int startIdx = 0;
	while (startIdx < N) {
		checkStackNum(startIdx);
		startIdx++;
	}

	while (stk.empty()==false) {
		int nowTopIdx = stk.top();
		resultVec[nowTopIdx] = -1;
		stk.pop();
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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