[leetcode][946] Validate Stack Sequences

문제 : https://leetcode.com/problems/validate-stack-sequences/

---

poped배열을 앞에서부터 탐색하면서 가능한 순서인지 체크한다.

pushed : 1 2 3 4 5

poped : 4 2 5 3 1 

를 예로 들어보자.

pop할 값	stack에 들어간 값	아직 stack에  들어가지 않은 값
		1 2 3 4 5
4	1 2 3	5
5	1 2 3
3	1 2
2	1
1

위 테이블을 보면 

pop해야 할 값이 아직 stack에 들어가지 않았다면 pop할 값이 나올 때까지 stack에 값을 넣는다.

pop해야 할 값이 이미 stack에 있다고 한다면 stack의 top에 해당하는 값이 해당 값이어야 한다.문제에서 조건을 보면 poped배열 크기와 pushed 배열크기는 같고 모든 배열요소들은 유니크하다고 했으므로 stack에 있어야만 할 뿐만 아니라 top에도 있어야 한다.

만약 top에 있는 값이 다음에 pop할 값이 아니라면 다른 값을 pop해야하고(이번에 pop한 값을 x라고 하자) 이후에 x를 pop해야할 때는 반드시 있을것이기 때문에 그때 어차피 틀린 경우가 된다.

시간 복잡도는 결과적으로는 pushed 값을 stack에 넣었다가 빼고 poped 배열 값들을 한 번 다 탐색하므로 O(N)이다.

---

소스코드 : https://gist.github.com/fpdjsns/69467fa4ef2bbf751e31a9ca18c21185

---

처음에는 스택에 넣었다가 뺐다 하기 싫어서 stack에 들어가야 하는 위치 인덱스(e)와 stack에 넣어야하는 pushed 배열 인덱스(s)만을 저장했었다.

stack에 들어가있는 값 = [0 ~ e) -> 포함하는 경우 -> [0 ~ ind) 갱신

아직 stack에 들어가있지 않은 값 = [s ~ N) -> 포함되는 경우 -> [ind+1 ~ N) 갱신

위와 같은 아이디어로 시작해서 인덱스 저장하는 map 추가하고 좀 더 정확성을 추가해서 코딩해서 제출했는데 Acceped가 떴었다.

그런데 찝찝해서 생각을 더 해보니

pushed = [1,2,3,4,5]

poped = [4,2,5,3,1]

인 경우 3이 pop되는 경우를 캐치해내지 못했다. (즉, 위에서 예시를 들었을 때 x 값과 같은 값을 캐치하지 못함)

TC 추가해야 될 것 같다고 토론글에 올려놓긴 했는데 맞겠지..?