[코딩테스트] 23/12/13 - 뒤에 있는 큰 수 찾기 (Level2)

🌜 프로그래머스 링크

문제 설명

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

제한사항

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

Github 링크

문제풀이

• stack을 사용하여 최적화해서 풀어야 시간오버가 안난다.

코드 (C++)

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    stack<int> s;
    s.push(0);
    for (int i = 1; i < numbers.size(); ++i)
    {
        while (!s.empty() && numbers[s.top()] < numbers[i])
        {
            answer[s.top()] = numbers[i];
            s.pop();
        }
        s.push(i);
    }
        
    return answer;
}

피드백

• for문을 두개사용할경우 On2 가되기때문에 시간오버가 생긴다.
• stack을 사용하여 이전값을 빠르게 조회할수있도록한다.

시간 오버된 코드 (C++)

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