뒤에 있는 큰 수 찾기

문제 설명

정수로 이루어진 배열 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]

 

---

문제 해설

 

for문을 2중for문으로 돌려서 해결해도 된다. 그러나, 그렇게 하면 시간초과가 나타나니, 동적계획법으로 데이터를 단계별로 참고하여 최소한의 반복을 이용해야한다.

 

또는, 스텍을 사용해서 큰 값들을 저장하면서 나아가도 된다.

---

첫 번째 시도

#include <string>
#include <vector>

using namespace std;

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

    for (int i = 0; i < numbers.size(); i++) {
        bool find = false;
        for (int j = i + 1; j < numbers.size(); j++)
        {
            if (numbers[i] < numbers[j]) {
                answer.emplace_back(numbers[j]);
                find = true;
                break;
            }
        }
        if (!find) answer.emplace_back(-1);
    }

    return answer;
}

실패

 

단순하게 이중for문으로 돌려서 객체를 찾게 하였다.

 

전부다 맞는 답이 나오지만, 악랄하게 시간초과를 걸어놓아서 틀리는 예제가 4개가 존재했다.

---

두 번째 시도

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    int nowmax = numbers.back();
    for (int i = numbers.size() - 1; i > 0; i--) 
    {
        if (numbers[i] > numbers[i - 1]) {
            answer[i - 1] = numbers[i];
        }
        else if(numbers[i - 1] < nowmax)
        {
            answer[i - 1] = nowmax;
        }
            
        if (nowmax < numbers[i]) nowmax = numbers[i];
    }

    return answer;
}

실패

 

시간초과를 해결하기 위해 반복문을 1개로 줄이고, 조건문을 간략하게 하였다.

 

현재 가장 큰 숫자를 저장하고, 일정 조건 하에 그 큰 수로 대입하게 하였다.

 

시간초과는 해결되었으나, 다른 예제들이 전부 틀렸다. 일단 시간초과가 왜 나타나는지 확인하는데 의의가 있었다.

 

---

세 번째 시도

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);

    for (int i = numbers.size() - 2; i >= 0; i--)
    {
        for (int j = i + 1; j < numbers.size(); j++)
        {
            if (numbers[i] < numbers[j])
            {
                answer[i] = numbers[j];
                break;
            }
            else if (numbers[i] >= numbers[j])
            {
                if (answer[j] == -1) break;
                else if (numbers[i] < answer[j])
                {
                    answer[i] = answer[j];
                    break;
                }
            }
        }
    }
    return answer;
}

성공

 

이중for문을 이용하되, 저장되는 최대값을 이용하는 대신 현재부터 마지막까지 순환하면서 다음값이 -1일경우, break 로 아닐때 numbers[i]가 answer[j]보다 작다면, 가장 근삿값의 큰 객체임으로, 해당 값을 대입 하였다.