Written by JS970
on February 1, 2023

1874 - 스택 수열

난이도: 실버 3
날짜: 2023년 2월 1일
상태: Correct
추가 검토 여부: No

solution

stack자료구조를 사용하여 원하는 입력받은 수열을 만드는 문제이다.
아래와 같이 경우의 수를 나누어 해결했다.
- 스텍이 빈 경우 → stack에 규칙에 따라 push
- 스텍에 원소가 있는 경우
  - stack top이 조건을 충족하는 경우 → pop or push
  - stack top이 조건을 충족하지 않는 경우 → break
cout << endl;의 구문에서 endl은 버퍼를 비우는 동작이 추가되므로 시간 초과가 발생하였다.
- 사실 cout자체도 printf보다 시간을 많이 사용하므로 printf를 사용하는 것이 맞는 것 같다.

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

int main()
{
    int stack_size;
    cin >> stack_size;
    int * elem = new int[stack_size];
    for(int i = 0; i < stack_size; i++)
        cin >> elem[i];

    int previous_inserted_elem = 0;
    int elem_cnt = 0;
    int prev_elem = 0;
    stack<int> stack;
    char * print_arr = new char[stack_size*2];
    int arr_idx = 0;

    while(elem_cnt < stack_size)
    {
        if(stack.empty())
        {
            for(int i = previous_inserted_elem+1; i <= elem[elem_cnt]; i++)
            {
                stack.push(i);
                print_arr[arr_idx++] = '+';
                previous_inserted_elem = i;
            }
        }
        if(stack.top() == elem[elem_cnt])
        {
            stack.pop();
            print_arr[arr_idx++] = '-';
            elem_cnt++;
        }
        else if(stack.top() < elem[elem_cnt])
        {
            if(previous_inserted_elem < elem[elem_cnt])
            {
                for(int i = previous_inserted_elem+1; i <= elem[elem_cnt]; i++)
                {
                    stack.push(i);
                    print_arr[arr_idx++] = '+';
                    previous_inserted_elem = i;
                }
            }
            else
            {
                break;
            }
        }
        else break;
    }

    if(arr_idx == stack_size*2)
        for(int i = 0; i < arr_idx; i++)
            cout << print_arr[i] << '\n';
    else
        cout << "NO" << endl;

    return 0;
}

ref

1874번: 스택 수열

Top