스택 순열

문제 설명

크기가 N인 고유한 요소의 두 배열 A와 B가 제공됩니다. 한 배열이 다른 배열의 스택 순열인지 확인하십시오.
스택 순열은 스택 및 스택 작업을 사용하여 하나의 어레이가 다른 어레이에서 생성될 수 있음을 의미합니다.

문제 설명 링크::https://practice.geeksforgeeks.org/problems/stack-permutations/1

Example 1:

Input:
N = 3
A = {1,2,3}
B = {2,1,3}
Output:
1
Explanation:
1. push 1 from A to stack
2. push 2 from A to stack
3. pop 2 from stack to B
4. pop 1 from stack to B
5. push 3 from A to stack
6. pop 3 from stack to B

Example 2:

Input:
N = 3
A = {1,2,3}
B = {3,1,2}
Output:
0
Explanation:
Not Possible

예상 시간 복잡도: O(N)

예상 보조 공간: O(N)

해결책

입력과 출력이 있을 때 스택 순열을 어떻게 확인할 수 있습니까? 가장 좋은 방법은 스택 자체를 복제하고 입력을 입력하는 것입니다.

또한 입력을 입력하는 동안 출력이 발생하면 출력이 스택을 자극해야 합니다. 즉, 요소를 팝아웃해야 합니다. 이것은 완료되어야합니다. 다음과 같은 불법 작업이 발생할 때마다 이러한 작업을 수행하는 동안

스택 언더플로 또는

출력 배열 반복이 완료되었지만 스택이 여전히 비어 있거나

스택 상단 및 출력 배열 반복 지점이 일치하지 않으며 순열을 검증하는 상황이 발생할 수 있다고 믿을 수 있는 다른 입력 작업이 없습니다.

이러한 유효하지 않은 경우에는 이 순열이 불가능함을 나타내는 명확한 답이 있습니다. 스택에 더 이상 요소가 없고 출력이 끝까지 만족되면 순열을 달성했다는 표시입니다.

class Solution {
    public static int isStackPermutation(int n, int[] ip, int[] op) {
        Stack<Integer> stack = new Stack<>();
        int opItr = 0;
        for(int i = 0; i < ip.length; i++) {
            while(opItr < op.length && !stack.isEmpty() && stack.peek() == op[opItr]) {
                stack.pop();
                opItr++;
            }
            stack.push(ip[i]);
        }
        while((opItr < n) && !stack.isEmpty() && (stack.peek() == op[opItr])) {
            opItr++;
            stack.pop();
        }
        return (opItr == n && stack.isEmpty())? 1 : 0;
    }
}