C++ 코딩테스트 강좌, 스택으로 오름차순 수열 만들기

문제 설명

주어진 수열의 숫자들을 스택을 이용하여 오름차순으로 정렬해야 합니다. 특정 숫자가 들어올 때마다, 현재 스택의 상태를 살펴보고 가능한 경우 오름차순 수열을 만들어내야 합니다. 만약 불가능할 경우, 적절한 메시지를 출력해야 합니다.

입력

• 첫 번째 줄에 정수 N(1 ≤ N ≤ 100,000)이 주어집니다. (N은 수열에서 숫자의 개수)
• 두 번째 줄에는 N개의 정수, 즉 수열이 주어집니다. (1 ≤ 수열의 각 정수 ≤ 1,000,000)

출력

• 수열을 오름차순으로 만들 수 있다면, ‘YES’를 출력합니다.
• 수열을 오름차순으로 만들 수 없다면, ‘NO’를 출력합니다.

예제 입력

        5
        4 3 6 8 5
        

예제 출력

        NO
        

풀이 과정

이 문제를 해결하기 위해서는 스택의 주요 속성을 효과적으로 활용해야 합니다. 우리는 숫자를 왼쪽에서부터 차례대로 읽어 스택에 넣고, 스택의 최상단 숫자가 현재 정렬해야 할 숫자와 일치하는지 확인합니다. 아래에 이 과정을 단계적으로 설명하겠습니다.

1단계: 입력 처리

먼저 입력된 숫자의 수를 읽고, 그에 따라 수열을 받아옵니다. 우리는 이 수열을 스택에 순서대로 넣고 처리할 예정입니다.

2단계: 스택을 이용한 수열 조작

각 숫자를 입력할 때마다 두 가지 작업을 수행해야 합니다.

• 현재 숫자를 스택에 푸시(push)합니다.
• 스택의 최상단 숫자가 우리가 목표로 하는 오름차순 수열의 다음 숫자라면, 스택에서 팝(pop)하여 결과로 출력합니다.

3단계: 불가능한 경우 처리

입력된 수열을 모두 처리했음에도 불구하고 목표 수열을 전부 출력하지 못했다면 ‘NO’를 출력하고 과정을 종료합니다.

4단계: 코드 구현

이제 이러한 과정을 C++ 코드로 작성해 보겠습니다.

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

using namespace std;

int main() {
    int N;
    cin >> N;

    vector sequence(N);
    for (int i = 0; i < N; i++) {
        cin >> sequence[i];
    }

    stack s;
    vector result;

    int next = 1; // 오름차순으로 정렬할 숫자
    for (int i = 0; i < N; i++) {
        s.push(sequence[i]); // 현재 숫자를 스택에 푸시합니다.

        // 스택의 최상단 요소가 next와 같은지 확인합니다.
        while (!s.empty() && s.top() == next) {
            result.push_back(s.top()); // 스택의 요소를 결과에 추가합니다.
            s.pop(); // 스택에서 팝합니다.
            next++; // 다음 숫자로 진행합니다.
        }
    }

    // 모든 숫자가 정렬되었는지 확인합니다.
    if (result.size() == N) {
        cout << "YES" << endl; // 성공적으로 오름차순 수열을 만들었습니다.
    } else {
        cout << "NO" << endl; // 실패했습니다.
    }

    return 0;
}
        

종합

이번 강좌에서는 스택을 활용하여 입력된 숫자들을 오름차순으로 정렬하는 방법을 배웠습니다. 스택의 특성을 이용하여, 실시간으로 숫자를 조작하면서 조건을 만족하는지 확인할 수 있었습니다. 코딩 테스트 문제에서 자료구조의 이해는 매우 중요하니, 앞으로도 다양한 문제를 통해 실력을 쌓아보시기 바랍니다.

더 나아가기

스택을 활용한 다양한 문제들이 존재합니다. 다음 번에는 큐(Queue)를 활용한 문제 혹은 다른 자료구조를 이용한 다양한 문제에 대해 다룰 예정입니다. 많은 관심 부탁드립니다!