백준 1874번 스택 수열: C언어 풀이 (C++, Python)

백준 1874 스택 수열 문제 해설입니다.
스택을 활용한 기본적인 방법과, 문제의 제한 조건을 활용환 최적화된 방법을 C언어로 상세히 설명합니다.
최종 코드는 C++과 파이썬 버전도 함께 적어두었습니다.

전략

스택 만들기

스택 수열이니 스택을 만들어준다.
수열의 원소가 주어졌을 때 필요한 조작을 push 파트와 pop 파트로 나눌 수 있다.

push 파트에서는 필요한 만큼 숫자를 스택에 넣어준다.
원소가 7이면 1부터 7까지 push해주면 된다. 이미 넣은 숫자는 다시 넣으면 안된다.
push_waiting 변수를 정의해서 1~n 중 얼마나 스택에 넣어는지를 저장한다.

pop 파트에서는 필요한 원소가 나올 때까지 pop해준다.
스택이 비었는데도 원소가 나오지 않으면 NO를 출력하고 프로그램을 종료하면 된다.

출력

push/pop 작업을 수행 할 때마다 "+"와 "-"를 곧바로 출력해주면 좋겠지만, 문제가 있다.
만약 주어진 수열이 스택 수열이 아니라면 "NO"를 출력해야 되기 때문이다.
스택 수열이 맞는 판정을 하기 전, 중간 과정에서 "+"나 "-"를 출력하면 안된다.

따라서 push 및 pop을 수행 할 때마다 이를 기록하는 배열을 만들어 준다.
최대 수열 크기 기준 push/pop 두 연산이 수행되므로 배열의 크기는 200000으로 잡는다.

코드

#include <stdio.h>

#define MAX_STACK_SIZE 100000
#define EMPTY -1

int main(void)
{
    int stack_size;
    scanf("%d", &stack_size);

    int stack[MAX_STACK_SIZE];
    int top = EMPTY;

    // Printed only if it's a valid stack series.
    char output_buffer[MAX_STACK_SIZE * 2];
    int buffer_count = 0;

    int push_waiting = 1;
    for (int i = 0; i < stack_size; i++)
    {
        int current_number;
        scanf("%d", &current_number);

        // Push
        while (current_number >= push_waiting)
        {
            stack[++top] = push_waiting++;
            output_buffer[buffer_count++] = '+';
        }

        // Pop
        while (stack[top] != current_number)
        {
            if (top == EMPTY)
            {
                printf("NO\n");
                return 0;
            }
            top--;
            output_buffer[buffer_count++] = '-';
        }

        top--;
        output_buffer[buffer_count++] = '-';
    }

    // Print result
    for (int i = 0; i < buffer_count; i++ )
    {
        printf("%c\n", output_buffer[i]);
    }
}

문제 제한 조건 이용하기

문제의 입력 조건을 잘 살펴보자.

n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

1이상 n이하의 정수가 n개 있고, 같은 정수가 두 번 나오는 일이 없다.
바꿔말하면 그냥 1 부터 n 까지 모든 수가 한 번씩 나온다는 말이다.

이제 8 - 5 - 4 - 3 - 2 - 7 로 이어지는 스택 수열을 생각해보자.
각 입력에 대한 스택 작동을 차근차근 시뮬레이션 해보기로 한다.

먼저 8을 입력받는다. 스택에 1부터 8까지 push하고, 이후 8을 pop한다.
다음 5를 입력받는다. 스택에서 7 6 5를 pop한다.

여기서 끝났다. 이미 스택 수열이 아니라는 것을 알 수 있다.
언젠가 나올 것이 분명한 7과 6의 pop이 불가능해졌기 때문이다.

더 나아가면, pop을 연속으로 두 번 이상 수행해야하면 이는 스택 수열이 아니다.
모든 원소가 자기 자신만을 pop해야 스택 수열이 되기 때문이다.
이를 이용하면 한결 더 간결한 코드를 작성할 수 있다.

C 코드

스택에 미리 0을 넣어두어 비었는지 체크할 필요를 없애두었다.

#include <stdio.h>
#include <stdbool.h>

#define MAX_STACK_SIZE 100001
int main(void)
{
    int stack[MAX_STACK_SIZE];
    int s_top = -1;

    char output_buffer[MAX_STACK_SIZE * 4];
    int buffer_count = 0;

    int num_inputs;
    scanf("%d", &num_inputs);

    stack[++s_top] = 0;
    int last_pushed = 0;
    int input_num;
    bool is_error = false;
    for (int i = 0; i < num_inputs; i++)
    {
        scanf("%d", &input_num);

        if (stack[s_top] <= input_num)
        {
            while (last_pushed < input_num)
            {
                stack[++s_top] = ++last_pushed;
                output_buffer[buffer_count++] = '+';
                output_buffer[buffer_count++] = '\n';
            }
            s_top--;
            output_buffer[buffer_count++] = '-';
            output_buffer[buffer_count++] = '\n';
        }
        else
        {
            is_error = true;
            break;
        }
    }

    if (is_error)
    {
        printf("NO\n");
    }
    else 
    {
        output_buffer[buffer_count] = '\0';
        printf("%s", output_buffer);
    }
}

C++ 코드

#include <iostream>
#include <sstream>

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr)

using namespace std;
int main()
{
    FASTIO;
    int num_inputs;
    cin >> num_inputs;

    constexpr int max_stack_size = 100000 + 1;
    int stack[max_stack_size];
    int s_top = -1;

    // Dummy value to prevent empty stack
    stack[++s_top] = 0;
    int last_pushed = 0;

    int input_num;
    stringstream output_buffer;
    for (int i = 0; i < num_inputs; i++)
    {
        cin >> input_num;
        if (stack[s_top] <= input_num)
        {
            while (last_pushed < input_num)
            {
                stack[++s_top] = ++last_pushed;
                output_buffer << "+\n";
            }
            s_top--;
            output_buffer << "-\n";
        }
        else
        {
            output_buffer.str("NO\n");
            break;
        }
    }

    cout << output_buffer.str();
}

파이썬

#!/usr/bin/env python3
import sys

n_integers, *integers = map(int, sys.stdin.buffer.read().splitlines())

stack = [0]
last_pushed = 0

is_valid_stack_seq = True
output = []

for i in integers:
    if stack[-1] <= i:
        while last_pushed < i:
            last_pushed += 1
            stack.append(last_pushed)
            output.append("+")
        stack.pop()
        output.append("-")
    else:
        # If stack[-1] > i, then we have to pop stack[-1] first to pop i
        # However, stack[-1] does exists in the sequence somewhere and 
        # it would not be able to be popped when the time comes
        is_valid_stack_seq = False
        break

if is_valid_stack_seq:
    sys.stdout.write("\n".join(output))
else:
    sys.stdout.write("NO")
sys.stdout.write("\n")