백준 s2 1874 스택수열 c++

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

​

풀이

계속 push하다가 원하는 수가 나오면 pop,

pop하고 나서 또 top이 원하는 숫자면 다시 pop <- 반복

​

생각해본 것

• endl 때문에 자꾸 시간 초과가 남
  • 참고 https://stackoverflow.com/questions/213907/stdendl-vs-n
  • endl == '\n' + std::flush
  • endl은 출력 버퍼도 비우기 때문에 \n과 시간 차이가 꽤 남
  • 아마 ps 시작할 때 endl보다 '\n'이 더 빠르다를 알고 시작해서 \n만 쓰다가, 최근에 까먹고 다시 씀

​

• input이 10^6인데, 10만 배열은 굳이 필요 없을 것 같아 그때 그때 cin으로 target 숫자를 받음
  • 마지막 target 숫자를 받고 또 불필요한 target을 받게 되므로, 예외처리 해줌 // if (tCnt == N)
  • 위 제출 목록에서 맨 위에가 그때 그때 cin으로 받아서 처리, 바로 아래가 input배열로 받아서 처리한 것
    • 메모리는 더 적게, 시간은 더 많이 걸림

​

• 메모리는 스택, 힙, 데이터로 구성 (참고 https://www.acmicpc.net/board/view/34836)
  • 스택: 함수 호출, 지역 변수, 매개 변수 (크기가 작은 편)
  • 힙: 사용자가 직접 할당
  • 데이터: 전역 변수, static
• 전역으로 선언했을 때, 보통 int는 10^8 개까지 가능
• 그래서 동적할당을 하면 배열 크기를 좀 더 늘릴 수 있음

/*boj s2 1874 스택 수열*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int N;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    stack<int> S;
    cin >> N;
    int target;
    vector<char> result;

    cin >> target;
    int tCnt = 1;
    for (int i = 1; i <= N; i++)
    {
        S.push(i);
        result.push_back('+');

        while (!S.empty() && S.top() == target)
        {
            result.push_back('-');
            S.pop();
            if (tCnt == N)
                break;
            cin >> target;
            tCnt++;
        }
    }

    // 출력
    if (S.empty())
    {
        for (char v : result)
        {
            cout << v << "\n";
        }
    }
    else
    {
        cout << "NO"
             << "\n";
    }
}