99클럽 코테 스터디 1일차 TIL 뒤에 있는 큰 수 찾기

뒤에 있는 큰 수 찾기

뒤에 있는 큰 수 찾기 문제 링크

문제 설명

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

처음 생각했던 솔루션

• 문제를 잘못 이해해서 dp 배열을 만들고 10^6으로 초기화해 그 값이 아닌 다른 값이 들어있으면 answer vector에 추가하는 방식으로 시도했다
• 해당 숫자에서 가장 가까이 있는 큰 수를 찾는 문제였기 때문에, 이런식으로 접근하면 안된다는 걸 찾음

문제풀이

• 숫자들의 배열에서 가장 뒤에 있는 숫자부터 탐색하는 방식을 채용했다.
• answer에 넣어준 숫자는 stack 에 넣어주고 top 에 있는 숫자가 현재 보고 있는 숫자보다 크다면 stack에 넣어주고
• 그게 아니라면 stack의 top이 현재 숫자보다 커질때까지 pop 을 하고, stack이 다 비워질 때 까지 숫자를 찾지 못하면 -1 를 answer에 넣어줬다.

코드

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

using namespace std;

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

    answer.push_back(-1);
    st.push(*(numbers.end() - 1));
    for (auto it = numbers.end()-2; it != numbers.begin()-1; it--) {
        if (st.top() > *it) {
            answer.push_back(st.top());
            st.push(*it);
        } else {
            while (!st.empty()) {
                if (st.top() > *it) {
                    answer.push_back(st.top());
                    st.push(*it);
                    break;
                }
                st.pop();
            }
            if (st.empty()) {
                st.push(*it);
                answer.push_back(-1);
            }
        }
    }

    reverse(answer.begin(), answer.end());

    return answer;
}

회고

• 요즘 알고리즘 문제를 풀면 거의 2차원 배열에서 Dfs, Bfs 하는 시뮬레이션 문제만 풀어서 그런지 해답이 잘 떠오르지 않고 많이 해맸다.
• 이번 코테 준비 스터디로 좀 극복 해야할듯