스택을 이용한 문제 풀이 - 오큰수

* Do it 코딩테스트를 참고하였습니다. - 백준 온라인 저지 17298번 문제

 

 해당 문제는 수열 A[i]의 오른쪽에 있는 수 중에서 A[i]보다 큰 수를 찾고, 가장 큰 수 중에서 가장 왼쪽에 있는 값을 찾는 문제입니다. (없는 경우 -1을 출력한다)

 

 해당 문제를 풀기 위해서는 스택을 이용하여야 합니다. 스택에 0번부터 인덱스를 넣고, A[S.top()]의 값이 A[i]의 값보다 작다면 A[i]의 값은S.top()인덱스의 오큰수가 됩니다. 반대로 크다면 오큰수가 아니게 되므로 i를 스택에 Push하여 스택안에 있는 값들에 대한 오큰수를 찾습니다. 마지막까지 스택안에 남아있는 값들은 오큰수가 존재하지 않으므로 해당 인덱스에 대한 출력은 -1을 하면 되는 것입니다.

 

 그럼 코드로 바로 알아보도록 하겠습니다.

void solution_012()
{
	int N;
	cin >> N;

	stack<int> S;
	vector<int> result(N);
	vector<int> list(N);
	for (int i = 0; i < N; i++)
		cin >> list[i];

	S.push(0);
	for (int i = 1; i < N; i++)
	{
		int num = list[i];

		while (!S.empty() && list[S.top()] < num)
		{
			result[S.top()] = num;
			S.pop();
		}
		S.push(i);
	}

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

	for (auto& i : result)
		cout << i << " ";

}

이상으로 문제에 대한 설명을 마치도록 하겠습니다. 포바~!