[C++] 백준 1874 스택 수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

1. 서론 

 

시간 초과만 조심하면 엄청 쉬운 문제... 시간 초과 때문에 시간 낭비 엄청함

 

2. 문제 풀이

 

1부터 n까지 순서대로 스택에 넣었다가 꺼내면서 수열을 만든다. 이때 문제에 제시된 수열이 가능한지, 가능한 경우에는 push 할 경우에 +, pop 할 경우에 -를 출력하고, 불가능한 경우에는 NO를 출력한다.

 

손으로 써보면서 하니까 금방 규칙을 찾았다.

 

1) 수열의 값이 나올 때까지 1부터 n까지 push, +를 다른 배열에 적어줌

2) 나올 경우 pop, 다음 값으로 넘어감, -로 적어줌

3) 수열이 끝날 때까지 1,2 반복

 

So 간단

 

 

3. 코드 설명

 

#include <stdio.h>
#include <stack>
#include <vector>

using namespace std;

int main()
{
    int n, i, x = 1, f = 1;
    int a[100000], b[100000];
    stack<int> s;
    vector<char> v;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    i = 0;
    while(i != n)
    {
        if (x <= a[i])
        {
            s.push(x++);
            v.push_back('+');
        }
        else if (s.top() == a[i])
        {
            b[i++] = s.top();
            s.pop();
            v.push_back('-');
        }
        else
            break;
    }

    for (i = 0; i < n; i++)
        if (a[i] != b[i])
           f = 0;

    if (f == 0)
        printf("NO\n");
    else
        for (i = 0; i < v.size(); i++)
            printf("%c\n", v[i]);
}

 

n은 수열의 개수고 a는 수열을 저장하는 배열, b는 반복문을 돌리며 값을 저장하는데 a 배열과 값이 같은지 아닌지 체크하기 위해 만든 배열이다.

반복문에서 x는 1~n까지의 수를 뜻한다. x가 수열 값과 같을 때까지 값을 계속 push 하고 만약 스택의 맨 위의 값이 수열의 값과 같으면 pop 하고 각각 +, -를 체크한다. 그리고 이에 해당되지 않는 경우에는 그냥 while문을 빠져나온다. (이거 없으면 무한 루프 돌아서 시간 초과 발생)

그리고 주어진 배열 a와, 만든 배열 b를 비교해 둘이 같으면 +, -를 적어뒀던 것을 출력, 아니면 NO를 출력한다.

 

+ 시간 초과 났던 이유

n의 100000까지인데 입출력은 n번보다 더 많이 일어날 확률이 높다. 그래서 cin, cout을 쓰면 메모리를 어마어마하게 잡아먹어서 시간 초과가 난다... 그래서 아예 iostream을 날리고 stdio.h를 소환해 printf, scanf를 썼다. 예전에 이런 적 있어서 깨달았지만 없었으면 어쩔 뻔.... ㅠ

 

++ 다른 사람들은 나처럼 b를 만들지 않고 반복문 안에서 no인지 아닌지 판단하던데 어떻게 하는지 모르겠음 (사실 알고 싶지 않음!)