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

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

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

틀린 풀이

• Naive approach

• 시간 초과

  테스트 20 〉 실패 (시간 초과)
  테스트 21 〉 실패 (시간 초과)
  테스트 22 〉 실패 (시간 초과)
  테스트 23 〉 실패 (시간 초과)
  채점 결과
  정확성: 82.6
  합계: 82.6 / 100.0

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

using namespace std;

const int SIZE = 1000001;

vector<int> solution(vector<int> numbers) {
    int N = numbers.size();
    
    vector<int> answer;
    for(int i = 0; i<N; ++i){
        int num = numbers[i];
        
        bool flag = false;
        for(int j = i+1; j<N; ++j){
            int next_num = numbers[j];
            if(num < next_num){
                answer.push_back(next_num);
                flag = true;
                break;
            }
            if(flag) break;
        }
        if(!flag) answer.push_back(-1);
    }
    return answer;
}

틀린 풀이

• 시간 초과

  테스트 21 〉 실패 (시간 초과)
  채점 결과
  정확성: 95.7
  합계: 95.7 / 100.0

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

using namespace std;

const int SIZE = 1000001;

vector<int> solution(vector<int> numbers) {
    int N = numbers.size();
    vector<int> closestBigger(SIZE, -1);
    vector<int> answer;
    for(int i = numbers.size()-1; i >= 0; --i){
        int num = numbers[i];
        answer.push_back(closestBigger[num]);
        for(int j = 1; j < num; ++j){
            closestBigger[j] = num;
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

풀이

• 스택 사용 풀이

numbers: 9, 1, 5, 3, 6, 2
answer: -1, 5, 6, 6, -1, -1

• answer -1로 초기화
  answer = {-1, -1, -1, -1, -1}

• 스택 원소 <숫자, 숫자 배열 내 인덱스>

• 스택 내 원소 내림차순 유지 하도록 push
  pop할 때 뒷 큰수(answer)계산 = 현재 push할 숫자

  • i=0, st: (9,0)
  • i=1, st: (9,0) (1,1)
  • i=2, st: (9,0) -> (1,1) pop, answer[1] = 5
    st: (9,0) (5,2)
  • i=3, st: (9,0) (5,2) (3,3)
  • i=4, st: (9,0) (5,2) -> (3,3) pop, answer[3] = 6
    st: (9,0) -> (5,2) pop, answer[2] = 6
    st: (9,0) (6,4)
  • i=5, st: (9,0) (6,4) (2,5)
  • answer = {-1, 5, 6, 6, -1, -1}

• 스택에 남은 모든 원소 하나씩 pop하기
  pop할 때 뒷 큰수(answer)계산 = -1 (생략 가능)

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

using namespace std;

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

📌참고자료

• 관련 문제 [프로그래머스] 주식가격