[프로그래머스] Level 2 : 뒤에 있는 큰 수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

입력으로 주어지는 배열의 길이가 1,000,000이기 때문에, 단순 계산으로는 20~23번 테스트케이스에서 시간 초과가 난다.

일반적인 2중 for문으로 계산

 

문제에서 뒤에있는 숫자 중, 자신보다 크면서 가장 가까이에 있는 수를 찾아야 한다.

뒷 큰수를 구하지 못한 수들을 저장하는 배열을 선언한다.

 

예를 들어, 뒷 큰 수를 구하지 못한 수가 {9, 5, 3}으로 있다고 하자.

뒷 큰수를 구하지 못한 수들은 모두 내림차순으로 배열에 저장된다.

(뒷 큰수를 구하지 못했다는 것은 아직 이 수들보다 큰 수가 들어오지 않았기 때문)

 

만약, 다음 수가 7이 들어온다고 하자.

그러면, 뒷 큰 수를 구하지 못한 수 배열에서 가장 먼저 3과 비교하여 3보다 큰지 확인한다.

3<7이니, 3의 뒷 큰 수는 7이 된다.

5<7이니, 5의 뒷 큰 수는 7이 된다.

9>7이니, 5는 뒷 큰수를 구하지 못한 수 배열에 들어가게 된다. {9, 7}

 

이 과정을 반복하게 되면, 마지막에 뒷 큰 수를 구하지 못한 내림차순 배열만이 남게 된다.

이들은 하나씩 꺼내며 뒷 큰수를 -1로 할당한다.

 

이 알고리즘은 Stack 자료구조를 활용하여 후입선출을 통해 구하면 비교적 간단하게 구현할 수 있다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> numbers) {
	vector<int> answer;
	stack<pair<int, int>> s;
	answer.resize(numbers.size());

	for (int i = 0; i < numbers.size(); ++i)
	{
		// 뒷 큰수를 구하지 못한 수의 배열
		int Size = s.size();
		while (Size--)
		{
			// 뒷 큰수를 발견했는가?
			bool Check = false;

			// 마지막에 배열에 들어온 수부터 비교 (후입선출)
			if (s.top().first < numbers[i])
			{
				answer[s.top().second] = numbers[i];
				s.pop();
				Check = true;
			}

			// 뒷 큰수를 발견하지 못했으면 넘어간다.
			if (!Check) break;
		}
		s.push({ numbers[i], i });
	}

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

	return answer;
}