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

문제

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

프로그래머스

---

문제 요약

정수로 이루어진 배열 numbers를 인자로 받아서 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 반환하는 함수 solution을 정의한다.

 

뒷 큰수: 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수

 

단, 뒷 큰수가 존재하지 않는 원소는 -1을 담는다.

---

코드

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

    stack<int> st;

    st.push(0);

    for (int i = 1; i < numbers.size(); i++) {
        while (!st.empty() && (numbers[i] > numbers[st.top()])) {
            answer[st.top()] = numbers[i];
            st.pop();
        }

        st.push(i);
    }

    return answer;
}

 

---

코드 설명

numbers의 길이가 1,000,000이므로, 하나의 뒷 큰수를 찾을 때마다 배열을 모두 탐색하면 O(N^2)의 시간복잡도로 인해 시간 초과 문제가 발생한다.

 

< 시간 초과 코드 >

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

    for (int i = 0; i < numbers.size(); i++) {
        int dist = 10000000;
        int back_big_number = 0;
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers[i] < numbers[j] && abs(i - j) < dist) {
                back_big_number = numbers[j];
                dist = abs(i - j);
            }
        }

        if (back_big_number == 0) {
            answer.push_back(-1);
        }
        else {
            answer.push_back(back_big_number);
        }

    }

    return answer;
}

 

따라서, 스택을 이용한다.

 

1. 스택을 하나 생성한다. 이 스택에는 아직 뒷 큰수를 찾지 못한 값의 인덱스를 삽입할 예정이다.

+ 먼저 배열의 첫번째 요소의 인덱스를 스택에 삽입한다.

 

2. 배열을 앞에서부터 순차적으로 접근하며, 스택 맨 위에 있는 값과 비교한다.

 

3. 만약, 현재 접근한 값이 스택 맨 위에 있는 값보다 더 크다면, 스택 맨 위에 있는 값의 뒷 큰수는 현재 접근한 값이 된다. 

=> answer[스택 맨 위에 있는 값의 인덱스] = 현재 접근한 값

 

4. 스택에 있는 수의 뒷 큰수를 찾았다면, 스택에서 꺼내고 새로운 맨 위에 있는 값의 뒷 큰수도 가능한지 반복해서 확인한다.

 

+ 위 과정이 모두 끝났음에도 스택에 남아 있는 수는 뒷 큰수가 없는 수이다. (-1 반환)