프로그래머스 2023.09.06 (2Lv 뒤에 있는 큰 수 찾기)

프로그래머스

문제

---

문제 설명
정수로 이루어진 배열 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]이 됩니다.

코딩

---

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer = {};
    answer.resize(numbers.size());
    stack<int> stack = {};

    for (int i = numbers.size() - 1; i >= 0; --i)
    {

        while (!stack.empty())
        {
            int inum = stack.top();
            if (numbers[i] < inum)
            {
                stack.push(numbers[i]);
                answer[i] = inum;
                break;
            }
            else
            {
                stack.pop();
            }
        }

        if (stack.empty())
        {
            stack.push(numbers[i]);
            answer[i] = -1;
        }
    }

    return answer;
}

처음 이중for문을 이용해 문제를 풀려했었다.

numbers의 0번째 인덱스부터 시작해서 해당 인덱스 뒤에 있는 인덱스들을 확인해, 제일 먼저 큰수가 나오면 answer에 push_back()을 해주고, 가장 마지막 인덱스까지 검사했어도 큰 수가 없었다면, -1을 넣어주려 했다.

 

하지만 코드를 짜기 전부터 numbers의 길이가 1,000,000이기 때문에 시간이 너무 오래걸릴 것 같았다.

처음에는 어떻게든 시간을 줄이기 위해 노력을 해봤으나, 특정 인덱스 보다 뒤에 있는 수들이 다 작다는 것을 확인하기 위해서는 무조건 모든 경우를 확인해야 했었다.

 

때문에 아에 뒤에서 부터 확인하면 어떨까를 생각했지만, 처음에는 앞에서 시작하든 뒤에서 시작하든 똑같다고 생각했다.

 

문제를 풀다 막혀서, 찾아보니 stack을 이용하라는 힌트를 봐서 스택을 사용해 풀게 되었다.

 

아직도 자료구조를 잘 사용하지 못하는 것 같아서 매번 사용하던 map이나 vector, list 외에도 좀 더 공부를 해야할 것 같다.

실행 결과

---