leetcode 946. Validate Stack Sequences

문제

https://leetcode.com/problems/validate-stack-sequences/description/

Validate Stack Sequences - LeetCode

스택의 push , pop 연산이 주어졌을때 valid한 연산인지 알아내는 문제

풀이

자바로 스택 문제를 풀이할때는 LinkedList 가 편하다. 리스트의 맨앞, 맨뒤 삽입 삭제 연산이 가능하기 떄문이다.

풀이는 다음과 같다.

1. pushed 배열을 선형 탐색하면서 리스트에 원소를 추가
2. 리스트의 마지막 원소(스택의 top) 가 popped[k] 랑 같다면 리스트 마지막 원소 삭제
3. pushed 배열탐색 끝난 후 리스트가 비어있는지 체크

코드

자바

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> l=  new LinkedList<>();
        int poppedIndex =0 ;
        for(int i = 0 ;i < pushed.length ;i++){
            if(poppedIndex == popped.length)return false;
            l.add(pushed[i]);
            while(!l.isEmpty() && l.peekLast() == popped[poppedIndex]){
                l.pollLast();
                poppedIndex++;
            }            
        }
        return l.isEmpty();
    }
}