서로 다른 값들로 구성된 두 개의 시퀀스 pushed와 popped가 주어졌을 때, 이 두 시퀀스가 처음에 비어 있던 스택에 대해 push와 pop 연산을 수행한 결과로 나타날 수 있는지 판별하는 문제입니다.
예를 들어 push = [1,2,3,4,5], pop = [4,5,3,2,1]이 입력으로 주어지면 출력은 true가 됩니다. 실제 연산 순서는 다음과 같습니다.
push(1) → push(2) → push(3) → push(4) → pop() : 4 → push(5) → pop() : 5 → pop() : 3 → pop() : 2 → pop() : 1
문제 해결 접근 방법
이 문제는 스택의 동작을 직접 시뮬레이션하면서 popped 배열과 일치하는지 확인하는 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- solve()라는 메서드를 생성합니다. 이 메서드는 pushed와 popped 배열을 인자로 받습니다.
- 스택 st를 정의하고, 인덱스(index)를 0으로 초기화합니다.
- i를 0부터 pushed 배열의 크기까지 반복합니다.
- pushed[i]를 스택 st에 push합니다.
- popped[index]가 스택의 top 요소와 같다면:
- index를 1 증가시킵니다.
- 스택에서 pop을 수행합니다.
- 스택이 비어 있지 않고 popped[index]가 스택의 top과 같은 동안 index를 증가시키며 계속 pop을 수행합니다.
- index가 popped 배열의 크기보다 작은 동안:
- popped[index]가 스택의 top과 같으면 index를 증가시키고 스택에서 pop합니다.
- 그렇지 않으면 루프를 종료합니다.
- 마지막에 스택이 비어 있다면 true를 반환합니다.
- 이 solve 메서드는 아래와 같이 호출됩니다.
- return solve(pushed, popped)
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& pushed, vector<int>& popped){
stack <int> st;
int currentIndexOfPopped = 0;
for(int i =0;i<pushed.size();i++){
st.push(pushed[i]);
if(popped[currentIndexOfPopped] == st.top()){
currentIndexOfPopped++;
st.pop();
while(!st.empty() && popped[currentIndexOfPopped]==st.top()){
currentIndexOfPopped++;
st.pop();
}
}
}
while(currentIndexOfPopped <popped.size()){
if (popped[currentIndexOfPopped]==st.top()){
currentIndexOfPopped++;
st.pop();
}else{
break;
}
}
return st.empty();
}
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
Solution s;
bool flag = s.solve(pushed, popped);
return flag;
}
};
main(){
vector<int> v = {1,2,3,4,5};
vector<int> v1 = {4,5,3,2,1};
Solution ob;
cout << (ob.validateStackSequences(v, v1));
}입력
[1,2,3,4,5] [4,5,3,2,1]
출력
1
복잡도 분석
이 알고리즘은 각 요소가 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)이며, 스택 저장 공간 때문에 공간 복잡도 역시 O(n)입니다. 여기서 n은 pushed 배열의 길이입니다.