스 택 의 유효한 출력 시퀀스 인지 아 닌 지 를 판단 합 니 다.

[문제 설명] 스 택 의 입력 순 서 를 제시 하고 이 스 택 에서 출력 할 수 있 는 지 여 부 를 판단 합 니 다.가능 하 다 면 유효 출력 을 위해 전체 스 택 횟수 를 되 돌려 주 고, 그렇지 않 으 면 무효 출력 으로 0 을 되 돌려 줍 니 다.시퀀스 의 입력 과 출력 은 모두 왼쪽 에서 오른쪽으로 이다.
1. 입 출력 순 서 는 모두 정수 이 고 중복 되 는 숫자 가 있 을 수 있 습 니 다.
2. 만약 에 하나의 숫자 가 입력 시퀀스 에 나타 나 지 않 지만 출력 시퀀스 에 나타 나 면 무효 출력 입 니 다.
3. 만약 에 하나의 숫자 가 입력 시퀀스 에 나타 나 지만 출력 시퀀스 에 나타 나 지 않 으 면 출력 은 입력 숫자 에 대해 스 택 작업 을 통 해 얻 을 수 있 고 효과 적 인 출력 입 니 다.
[입력 형식] 첫 번 째 줄 은 두 개의 숫자 를 포함 합 니 다. 입력 시퀀스 의 길이 와 출력 시퀀스 의 길이 입 니 다.두 번 째 행위 입력 시퀀스 의 숫자;세 번 째 행위 출력 시퀀스 의 숫자.입력 데 이 터 를 빈 칸 으로 분리 합 니 다.
[출력 형식] 효과 적 인 스 택 시퀀스 라면 전체 스 택 횟수 를 되 돌려 줍 니 다. 그렇지 않 으 면 0 [샘플 입력 1] 을 되 돌려 줍 니 다.
5 5
1 2 3 4 5
4 5 3 2 1
[샘플 출력] 5 [샘플 설명]
다음 순서대로 실행 할 수 있 습 니 다:
push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
5 회 pop 작업 을 통 해 출력 시퀀스 를 얻 을 수 있 으 므 로 5 로 되 돌려 줍 니 다.
[샘플 입력 2]
5 5
1 2 3 4 5
4 3 5 1 2
[샘플 출력] 0 [샘플 설명]
1. 2 전에 출력 할 수 없 기 때문에 0 으로 돌아 갑 니 다.
문제 분석
이 문 제 를 해결 하면 우 리 는 스 택 을 신청 한 후에 입력 시퀀스 에서 출력 시퀀스 와 같은 지 아 닌 지 를 판단 하 는 머리 를 시작 할 수 있다.간단 한 예 를 들다.예 를 들 어 입력 서열 은 1, 2, 3, 4 출력 서열 은 3, 4, 2, 1 이다. 이것 은 출력 서열 의 첫 번 째 숫자 는 3 이다. 우 리 는 입력 서열 부터 3 을 찾 고 3 을 찾 을 때 까지 한다. 만약 에 3 전에 데이터 가 있 으 면 우 리 는 이 를 스 택 에 저장한다. 입력 서열 에서 1 요 소 를 만 나 기 시 작 했 고 출력 서열 의 첫 번 째 요소 와 같 지 않 으 면 우 리 는 1 을 스 택 에 넣 었 다.그 다음 에 2 요소 도 기다 리 고 싶 지 않 고 스 택 에 넣 었 습 니 다. 그 다음 에 3 입 니 다. 이때 출력 서열 의 첫 번 째 요소 와 같 습 니 다. 우 리 는 출력 서열 의 아래 표 지 를 2 로 옮 겼 고 입력 서열 의 아래 표 지 를 3 으로 옮 겼 습 니 다. 이때 출력 서열 의 요 소 는 4 입 니 다. 먼저 스 택 꼭대기 요 소 를 비교 한 결과 같 지 않 습 니 다. 이때 요 소 는 입력 서열 의 뒤에 있 거나 없 거나.우 리 는 입력 서열 에서 찾 습 니 다. 이때 의 출입 서열 은 요소 4 가 출력 서열 의 요소 와 똑 같다 는 것 을 말 합 니 다. 그래서 우 리 는 출력 서열 과 입력 서열 의 아래 표 지 를 모두 1 을 더 했 습 니 다. 이때 입력 서열 은 이미 다 되 었 고 출력 서열 은 2 를 가리 키 며 우 리 는 먼저 스 택 꼭대기 요소 와 비교 한 결과 이들 이 똑 같다 는 것 을 알 게 되 었 습 니 다. 그래서 우 리 는 스 택 꼭대기 요 소 를 삭제 합 니 다.이 동시에 출력 서열 의 아래 표 시 는 1 을 추가 합 니 다. 이때 출력 서열 은 요소 1 까지 입 니 다. 우 리 는 스 택 꼭대기 요소 와 비교 한 결과 똑 같 습 니 다. 그래서 우 리 는 스 택 꼭대기 요 소 를 삭제 하 는 동시에 출력 서열 의 아래 표 시 는 1 을 추가 합 니 다.이때 우 리 는 스 택 이 비어 있 는 것 을 발 견 했 고 입력 시퀀스 의 아래 표 지 는 입력 시퀀스 의 끝 에 이 르 렀 습 니 다. 이것 은 출력 시퀀스 가 스 택 의 출력 시퀀스 임 을 설명 합 니 다. 우 리 는 true 로 돌아 갑 니 다. 그렇지 않 으 면 우 리 는 false 로 돌아 갑 니 다.
의사 코드

     ，
cin>>    out
cin>>    in
                 
    cout<<0;return 0;
   ，            (in)     push

for(int index_out=1,index_out<out_length;i++){
     
	if(   &&  ==out[index_out]){
     //        ！！！             1234，             ，    push  。
		pop（    ）
	}
	else{
     
	 in[index_in]   
	while（flag==0）{
     
	if(   ){
     cout<<0;return 0;}//      ，             ，                        。               。      flag，     flag=1
	else            flag=1;
	}
	}
}
cout<<out_length;//           

코드

//              
#include 
#include 
#include 
using namespace std;
int main() {
     
    stack<int>tmp;int in_length=0;int out_length=0;int i=0;int index_in=0;int flag=0;
    int index_out=0;
    cin>>in_length>>out_length;
    if(in_length<out_length){
     
        cout<<0;
        return 0;
    }
  //  int *in=new int[in_length];
 //   int *out=new int[out_length];
    int in[100000]={
     0};
    int out[100000]={
     0};
    for (i=0; i<in_length; i++) {
     
        cin>>in[i];
    }
    for (i=0; i<out_length; i++) {
     
        cin>>out[i];
    }
    while (in[index_in]!=out[index_out]&&index_in<in_length) {
     
        tmp.push(in[index_in]);
        index_in++;
    }
    if(index_in==in_length){
     
        cout<<0;
        return 0;
    }//        
  
    else{
     
        for (index_out=1; index_out<out_length; index_out++) {
     
            if(!tmp.empty()&& tmp.top()==out[index_out]){
     
                tmp.pop();
            }
            else{
     flag=0;
                          index_in++;
                
                while(flag!=1){
     
                    if (index_in==in_length-1) {
     
                        if (in[index_in]==out[index_out]) {
     
                            flag=1;
                        }
                        else {
     
                            cout<<0;
                            return 0;
                        };
                    }
                    else if(index_in==in_length){
     cout<<0;return 0;}
                    else{
     
                        if(in[index_in]==out[index_out]){
     
                            flag=1;
                        }
                        else{
     
                            tmp.push(in[index_in]);
                            index_in++;
                        }
                    }
                }
            }
        }
    }
    cout<<out_length<<endl;
  //  delete []in;
  //  delete []out;
}

계시
4. 567917. 이번 문 제 는 비교적 빠 른 데 위조 코드 를 먼저 쓰 고 생각 을 밝 혀 서 문 제 를 풀 었 기 때문에 앞으로 도 계속 이렇게 해 야 한다.어 지 럽 고 미 친 debug 의 상황 을 피하 세 요
4. 567917. 용기 에 대해 pop, top 전에 비 어 있 는 지 확인 해 야 합 니 다.