[2] 뒤에 있는 큰 수 찾기 (Stack, 이중순회X)

문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항
4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000
입출력 예
numbers result
[2, 3, 3, 5] [3, 5, 5, -1]
[9, 1, 5, 3, 6, 2] [-1, 5, 6, 6, -1, -1]

입출력 예 설명
입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

---

문제풀이
제한사항을 보면 이중포문 안됨
Stack을 활용한다.
값의 인덱스를 스택에 넣고, 현재 값을 스택에 들어가 있는 인덱스 원소 값과 비교한다.

 

느낀점

이중순회는 시간초과 되어 다른 풀이방법을 고민했지만 떠오르지 않았다.

이렇게 풀어야 겠다는 생각은 어떻게 나오는건지;

유형을 확실히 기억하자

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
	vector<int> answer(numbers.size(), -1);
	stack<int> stack; // 바뀌지 않은 idx 저장
	for (int i = 0; i < numbers.size(); i++)
	{
		while (stack.empty() == false)
		{
			if (numbers[stack.top()] >= numbers[i])
				break;
			else
			{
				answer[stack.top()] = numbers[i];
				stack.pop();
			}

		}
		stack.push(i);
	}

	return answer;
}