PAT A 1051(1급)

1051 Pop Sequence(25점)
지은이: 첸, 유
단위: 절강대학
시간 제한: 400ms
메모리 제한: 64MB
코드 길이 제한: 16KB
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES"if it is indeed a possible pop sequence of the stack, or "NO"if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

 
 
이 문제는 1~N을 이런 순서로 출고할 수 있는지를 일정한 조건하에서 판단하는 서열의 숫자를 제시하는 것이다.
그러면 사실 우리는 전체 과정을 모의하여 판단할 수 있다. j=1은 현재 창고에 압입될 숫자이고 i로 입력 서열의 하표를 대표한다.
다음은 아주 뚜렷한 두 가지 상황이 생길 것이다.
1. 창고가 비어 있을 때, 우리는 j++를 창고에 눌러 넣는다
2. 창고가 비어 있지 않을 경우 일정한 판단을 수행한다.
다음은 스택 상단 요소와 현재 시퀀스 요소를 비교하는 것입니다.
1. 서열 원소가 창고 꼭대기 원소보다 크면 우리는 이어서 j++를 창고에 눌러 다음 순환을 진행할 수 있다
2. 만약에 서열 원소가 창고 꼭대기 원소보다 작다면 이때 우리는 이 순서로 창고에 나올 수 없다는 것을 확신할 수 있다. 창고 꼭대기 원소가 서열 원소보다 크면 출력해야 하는 서열 원소가 창고 안에 있다는 것을 증명하고 이 원소를 출력하려면 반드시 창고 꼭대기 원소를 출력해야 한다. 이때 우리가 원하는 서열이 아니기 때문에 이 순서로 창고에 나올 수 없다.
3. 둘이 같다. 이것은 가장 기쁜 상황이다. 이때 우리는 창고 꼭대기 요소를 창고에서 꺼내고++i는 다음 서열 요소를 검사한다.
또한 제목에서 정한 창고 용량과 기타 제한 조건을 잊지 마십시오. Stack.사이즈 () > 최대 용량일 때는 이 순서로 출고할 수 없다는 뜻이기도 하다. 같은 결과를 낳을 때는 또 무엇이 있을까. 바로 j > n + 1일 때(왜 n + 1은 n이 아닐까. 마지막으로 j가 눌린 후에도 j를 +1 조작하기 때문에 j는 n보다 크지만 n + 1보다 크지 않을 것이다).
그럼 끝 조건은 무엇입니까? 서열의 마지막 요소를 검사했을 때 끝낼 수 있습니다. 즉, i>=n일 때true로 돌아갑니다.
 
 
AC 코드:

#include 
#include 

using namespace std;

int se[1010];

bool correct(int, int);

int main() {
    stack is;
    int m, n, k;

    scanf("%d%d%d", &m, &n, &k);
    for(int i = 0; i < k; ++i) {
        if(correct(m, n)) {
            printf("YES
");
        } else {
            printf("NO
");
        }
    }

    return 0;
}

bool correct(int m, int n) {
    stack is;
    for(int i = 0; i < n; ++i) {
        scanf("%d", se + i);
    }
    int i = 0, j = 1;
    while(1) {
        if(is.empty()) {
            is.push(j++);
        } else {
            if(is.top() < se[i]) {
                is.push(j++);
            } else if(is.top() > se[i]) {
                return false;
            } else {
                is.pop();
                ++i;
            }
        }

        if(is.size() > m) {
            return false;
        }

        if(i >= n) {
            return true;
        }

        if(j > n + 1) {
            return false;
        }
    }
}

 
 
잘못이 있으면 지적을 환영합니다.