[프로그래머스/C++ 문제 풀이] Lv. 2 - 뒤에 있는 큰 수 찾기

문제 설명

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

제한 사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

입출력 예

 

입출력 예 #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]이 됩니다.

---

문제 풀이

이번 문제는 전체 숫자를 순회하며 해당 숫자의 뒷 방향으로 가장 가까운 숫자를 찾는 문제입니다.

 

처음에는 2중 for문을 활용해 i번째 숫자보다 j번째 숫자가 큰 경우가 올 때까지 순회하는 방식으로 무식하게 문제를 풀었으나, numbers 배열의 길이가 1,000,000 이므로 최대 시간 복잡도가 1,000,000,000,000이 되며 시간 초과를 받게 되었습니다.

 

두 번째로 시간복잡도를 줄이기 위해 1번의 for문만을 사용하는 방식을 생각해보다 stack을 사용하게 되었으며, 전체 수를 뒤집은 상태로 스택에 쌓아가며 기존 스택의 내용과 비교해 결과를 도출하는 방식으로 문제를 해결하게 되었습니다.

 

예를들어 1 5 3 4 6이라는 수가 있다면 결과물은 5 6 4 6 -1이 되어야 합니다.

 

우선 원본 배열을 뒤집으면 6 4 3 5 1이 되며, 순서대로 스택에 쌓아갑니다.

(맨 마지막 숫자는 뒤에 무조건 해당 숫자보다 큰 수가 없으므로 -1을 넣어주면 됩니다.)

 

처음에는 6이 스택에 남아있으며, 다음에 4가 들어오며 기존 스택의 6과 비교하게 됩니다.

6은 4보다 작으므로, 스택에 4라는 숫자를 추가하고 결과물에 6을 추가하면 됩니다.

 

다음으로 3이 들어오게 되면 스택의 최상단인 4와 비교하여 위와 동일하게 4를 결과물에 추가하게 됩니다.

 

다음으로 5가 들어오면 스택의 최상단 3보다 크므로 3을 스택에서 제거하며, 해당 방식으로 스택이 비기 전까지 5보다 큰 수를 찾습니다.

즉, 스택의 하단에 위치한 6을 만나기 전까지 순회하며 6을 만나는순간 6을 결과물에 추가하고 5를 스택에 넣습니다. 

 

마지막으로 1이 들어오게 되면 5와 비교하게 되며, 5를 결과물에 추가하고 반환합니다.

즉, -1 6 4 6 5가 나오게 되며 해당 결과물을 뒤집으면 5 6 4 6 -1로 처음에 예상했던 결과물과 동일한 수를 얻을 수 있습니다.

 

만약 중간에 위치한 수가 가장 큰 수 (ex. 1 9 1)라면 위와 같은 과정에서 9를 비교할 때 스택이 전부 비게 되며, 스택이 전부 빈 경우 무조건 뒤에 해당 숫자보다 큰 수가 없는 것으로 생각하여 -1을 결과물에 추가해주는 방식이 되게 됩니다.

정답 코드

풀이 시간 : 23m 11s

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;

    stack<int> stk;

    reverse(numbers.begin(), numbers.end());

    stk.push(numbers[0]);
    answer.push_back(-1);
    for (int i = 1; i < numbers.size(); i++)
    {
        if (stk.top() > numbers[i])
        {
            answer.push_back(stk.top());
            stk.push(numbers[i]);
        }
        else
        {
            stk.pop();

            while (true)
            {
                if (stk.empty())
                {
                    stk.push(numbers[i]);
                    answer.push_back(-1);
                    break;
                }

                if (stk.top() > numbers[i])
                {
                    answer.push_back(stk.top());
                    stk.push(numbers[i]);
                    break;
                }
                else
                {
                    stk.pop();
                }
            }
        }
    }

    reverse(answer.begin(), answer.end());

    return answer;
}