스택

스택으로 수열 만들기

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

파악

스택에 push할 값들이 자연수이고 pop이 출력

구상

스택 S, 출력 스택 PS
원소를 입력받을 때마다 S[top] 검사할 것
스택 S는 자연수의 순서대로 입력받기에, 최초 입력값의 S[top]은 입력값과 같음

• 다만 이후의 입력값들이 순서대로 들어오지 않기에, S[top]과 같은지 확인 $\rightarrow$ 같지 않다면 그 수열을 만들 수 없음

구현

자료형(배열로 스택 구현)

vector <int> S;
vector <char> P;

입력

for(int i =0; i<N; i++){
	int E;
	cin >> E;
}

top에 입력값이 들어올 때 까지 자연수(num) 값을 오름차순으로 push

• 문제 조건에 따라 1부터 ++

        while (num <= E){ // top에 입력값이 들어올 때까지 자연수값을 오름차순으로 push
            S.push_back(num);
            P.push_back('+');
            num++;
        }

조건검사

S[top]에 입력값이 있으면 pop(), S[top] > E인지 확인

        int top = S.size()-1;

        if (S[top] == E){ //top = S.size()-1
            S.pop_back();
            P.push_back('-');
        }

        else if (S[top] > E){
            result = false;
        }
        //while문으로 인해 S[top]가 E보다 작은 경우는 없다.
    }

출력

    if (result == true){
        for (int i = 0; i <P.size(); i++){
            cout << P[i] << "\n";
        }
    }
    else if(result == false){ // 중간에 입력이 끊기면 안돼서 for-문 밖에서 출력
        cout << "NO" << "\n";
    }