C++ 코딩테스트 강좌, 오큰수 구하기

이번 강좌에서는 C++을 사용하여 “오큰수 구하기”라는 문제를 해결해보겠습니다. 이 문제는 주어진 수열에서 각 원소에 대해 자신보다 크고, 가장 가까운 위치에 있는 수를 찾는 문제입니다. 이를 통해 스택을 활용한 문제 해결 방법과 효율적인 알고리즘 설계를 배워보겠습니다.

문제 설명

주어진 정수 배열에서 각 배열의 원소에 대해, 그 원소보다 큰 수가 오른쪽에 있는 가장 가까운 위치를 찾아 해당 수를 출력합니다. 만약 그런 수가 존재하지 않는다면 -1을 출력해야 합니다.

입력

첫 번째 줄에 배열의 크기 N (1 ≤ N ≤ 1,000,000)
두 번째 줄에 N개의 정수로 이루어진 배열 A (0 ≤ A[i] ≤ 1,000,000)

출력

N개의 정수로 이루어진 배열 B를 출력해야 하며, B[i]는 A[i]의 오른쪽에서 가장 가까운 큰 수입니다. 그런 수가 없다면 -1을 출력해야 합니다.

예제 입력


5
2 1 2 4 3

예제 출력


4 2 4 -1 -1

문제 접근 방법

이 문제를 해결하는 가장 효율적인 방법은 스택(Stack) 자료구조를 사용하는 것입니다. 배열의 맨 뒤에서부터 시작하여 각 원소를 순회하면서 다음과 같은 과정을 수행합니다.

스택이 비어있지 않고, 현재 원소가 스택의 가장 위에 있는 원소보다 크면, 스택에서 원소를 pop 합니다. 이 때 pop한 원소는 현재 원소의 오큰수가 됩니다.
현재 원소의 인덱스와 오큰수 값을 배열에 저장합니다.
현재 원소를 스택에 push합니다.

이 과정을 배열의 처음까지 반복하여 모든 원소의 오큰수를 찾을 수 있습니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. 각 원소는 스택에 단 한 번 push되고 단 한 번 pop되므로, 모든 원소를 들른다고 하더라도 스택의 원소 개수는 N을 넘지 않습니다.

구현

이제 실제로 위의 알고리즘을 C++로 구현해보겠습니다.


#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void findNextGreaterElement(const vector<int>& arr, vector<int>& result) {
    stack<int> s; // 스택 선언

    for (int i = arr.size() - 1; i >= 0; --i) {
        // 스택에서 현재 원소보다 작거나 같은 원소를 제거
        while (!s.empty() && s.top() <= arr[i]) {
            s.pop();
        }
        // 스택이 비어있으면, 오큰수는 -1
        if (s.empty()) {
            result[i] = -1;
        } else {
            result[i] = s.top(); // 스택의 가장 위 원소가 오큰수
        }
        s.push(arr[i]); // 현재 원소를 스택에 추가
    }
}

int main() {
    int N;
    cout << "배열의 크기를 입력하세요: ";
    cin >> N;

    vector<int> arr(N);
    cout << "배열 원소를 입력하세요: ";
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    vector<int> result(N);
    findNextGreaterElement(arr, result);

    cout << "오큰수: ";
    for (int i = 0; i < N; ++i) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

코드 설명

위의 코드는 “오큰수 구하기” 문제를 해결하기 위한 C++ 프로그램입니다. 다음은 각 부분에 대한 설명입니다.

헤더 파일 포함: iostream, vector, stack 라이브러리를 포함하여 입출력, 벡터 사용, 스택 사용을 가능하게 합니다.
findNextGreaterElement 함수: 이 함수는 입력으로 주어진 배열과 결과를 저장할 벡터를 받아, 오큰수를 찾는 핵심 로직을 포함하고 있습니다.
main 함수: 프로그램의 시작점으로, 사용자로부터 배열의 크기와 원소를 입력받고, 오큰수를 계산한 후 결과를 출력합니다.

결론

이번 강좌에서는 “오큰수 구하기” 문제를 C++을 사용하여 효율적으로 해결하는 방법을 배웠습니다. 스택을 활용하여 배열의 각 원소에 대해 오큰수를 찾아내는 과정에서 스택의 특징과 알고리즘의 효율성을 느낄 수 있었습니다. 실제 코딩 테스트에서는 이러한 자료구조와 알고리즘을 활용할 수 있는 능력이 중요합니다.

코딩테스트에서 자주 출제되는 문제인 만큼 다양한 변형 문제에 대해서도 고민해보고, 스택을 활용한 문제 해결 능력을 키우는 것이 중요합니다. 앞으로도 유사한 문제들을 접하면서, 다양한 알고리즘과 자료구조를 익혀보시기 바랍니다.