[프로그래머스][C++][154539] 뒤에 있는 큰 수 찾기

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

1. 문제

설명

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

 

2. 설명

https://sayho98.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C42584-%EC%A3%BC%EC%8B%9D-%EA%B0%80%EA%B2%A9

 저번에 풀었던 문제와 상당히 유사하였습니다. 저번에 풀었을때는 마지막에 값들을 계산해주어야 했지만 이번에는 -1로 놓으면 되어 더 간단하였습니다.

 

 전의값들은 deq에 저장시킨뒤, 현재의 값(numbers[i ])과의 비교를 통해 진행하였습니다.

 

deq.front().first (가장최근의 값)   < numbers[i]  인경우 크기가 큰 경우이므로 갱신해줍니다. 이때 한번만 하는게 아닌 전의 값들도 while문을 통해 확인해주어야 합니다. 와일문을 돌다가 deq.front().first >=numbers[i] 인경우 뒷큰수가 아니므로 다음으로 넘어갑니다.

3. 코드

#include <string>
#include <vector>
#include <deque>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(),-1);
    
    deque <pair<int,int>> deq; //값, 위치
    
    for(int i=0; i<numbers.size(); i++){
        
       while(deq.empty()!=1){    
           if(deq.front().first>=numbers[i])
               break;
           
           answer[deq.front().second]=numbers[i];
           deq.pop_front();
       }
        
        deq.push_front({numbers[i],i});        
    }
    
    return answer;
}