본문 바로가기

Problem Solving/문제풀이

[BOJ] 1874 스택 수열

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


굉장히 간단해 보이는 문제와 굉장히 간단한 해법이다.

그저 숫자를 스택에 차례대로 넣으면서 지금 빼야 하는 숫자가 top이면 pop해주면 된다.

만약에 모든 알고리즘이 끝났는데도 stack이 비지 않았다면 NO.


코드를 좀 더 깔끔하게 짤 수 있을 것 같다. 고민 좀 해 봐야징

아마 난이도는 1/5 정도


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stack>
#include <vector>
 
using namespace std;
 
stack<int> S;
vector<char> oper;
 
int main()
{
    int i=1,j=1,n,arr[100005];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    while(j<=n)
    {
        if(!S.empty() && S.top()==arr[i])
        {
            i++;
            S.pop();
            oper.push_back('-');
        }
        else
        {
            S.push(j++);
            oper.push_back('+');
        }
    }
    while(!S.empty())
    {
        if(arr[i]==S.top())
        {
            i++;
            S.pop();
            oper.push_back('-');
        }
        else
            break;
    }
    if(S.empty())
    {
        for(vector<char>::iterator it=oper.begin();it!=oper.end();it++)
            printf("%c\n",*it);
    }
    else
        printf("NO");
 
    return 0;
}
 
cs


'Problem Solving > 문제풀이' 카테고리의 다른 글

[BOJ] 2439 탑  (0) 2018.02.01
[BOJ] 1011 Fly me to the Alpha Centauri  (1) 2018.02.01
[BOJ] 1918 후위표기식  (0) 2018.02.01
[BOJ] 3986 좋은 단어  (0) 2018.02.01
[BOJ] 2841 외계인의 기타 연주  (0) 2018.02.01