[Algorithm] Baekjoon 1874번 : 스택 수열

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

1874번: 스택 수열

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n; 
 
    cin >> n;
 
    string answer = "";
    stack<int> s;
    int target;
    int lastNum = 0;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> target;
 
        while (lastNum < target)
        {
            ++lastNum;
            s.push(lastNum);
            answer += '+';
        }
 
        if (s.top() == target)
        {
            answer += '-';
            s.pop();
        }
        else
        {
            cout << "NO";
            return 0;
        }
    }
 
    for (int i = 0; i < answer.size(); ++i)
    {
        printf("%c\n", answer[i]);
    }
}
 

문제의 포인트?를 못찾아서 실버2임에도 불구하고 꽤 오래 걸렸다...

 

이 문제에서의 포인트는 '절대로' 안되는 지점을 찾아서 바로 반복문을 종료시키는 것에 있다.

문제의 조건상, pop을 해버린 숫자는 다시 push할 수가 없다. 

그렇기 때문에 자기가 push했던 마지막 숫자보다 더 작은 숫자를 꺼내려면, 지금 바로 스택의 top에 있을때 빼고는 절대 꺼낼 수 없다. 

왜? 그 작은숫자 꺼내려고 싹다 pop해버리면 이후에 절대 수열을 완성시킬 수 없기 때문이다.

그렇기 때문에 target값이 lastNum(마지막에 push했던 숫자) 작을 경우, top에 없다면 바로 NO를 출력해버리고 종료시키면 된다.