[Baekjoon(백준)][17298번] 오큰수(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "오큰수 " 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 수열에서 각 원소의 오른쪽에 있으면서 해당 원소보다 큰 수 중 가장 왼쪽에 있는 수를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

https://www.acmicpc.net/problem/17298

17298번: 오큰수

문제 개요

오큰수 문제는 주어진 수열에서 각 원소의 오른쪽에 있으면서 해당 원소보다 큰 수 중 가장 왼쪽에 있는 수를 찾는 문제입니다. 만약 해당하는 수가 없을 경우 -1을 출력합니다.

해결 전략

이 문제는 스택을 활용하여 효율적으로 해결할 수 있습니다. 수열의 각 원소를 순회하면서, 스택에는 아직 오큰수를 찾지 못한 원소들의 인덱스를 저장합니다. 새로운 원소를 만날 때마다 스택의 top에 있는 원소들과 비교하여 오큰수를 찾으면 스택에서 해당 원소들을 제거하고, 오큰수를 결과 배열에 저장합니다.

코드 구현

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; // 수열의 크기
    cin >> n;

    vector<int> ret(n, -1); // 결과 배열, 오큰수를 저장. 초기값은 -1.
    vector<int> table(n, -1); // 입력받은 수열
    stack<int> s; // 스택, 아직 오큰수를 찾지 못한 원소들의 인덱스 저장

    // 수열의 원소를 입력받으면서 오큰수 찾기
    for (int i = 0; i < n; i++) {
        cin >> table[i]; // 수열의 원소 입력
        // 스택이 비어있지 않고, 현재 원소가 스택 top의 원소보다 큰 경우
        while (s.size() && table[s.top()] < table[i]) {
            ret[s.top()] = table[i]; // 오큰수를 결과 배열에 저장
            s.pop(); // 스택에서 제거
        }
        s.push(i); // 현재 원소의 인덱스를 스택에 저장
    }

    // 결과 출력
    for(int i = 0; i < n; i++) {
        cout << ret[i] << " ";
    }

    return 0;
}

코드 설명

위 코드는 입력받은 수열의 각 원소에 대해 오큰수를 찾아 결과 배열에 저장합니다. 스택을 활용하여 오큰수를 효율적으로 찾으며, 모든 원소에 대해 오큰수를 찾은 후 결과 배열을 출력합니다.

결론

스택을 활용하면, 각 원소의 오큰수를 효율적으로 찾을 수 있습니다. 이 방법을 사용하면, 각 원소를 한 번씩만 확인하면 되므로 시간 복잡도는 O(n)입니다.