2n개의 문자가 있고 각각에 1에서 n 사이의 정수가 쓰여 있다고 가정합니다. 정확히 같은 숫자가 쓰여진 두 글자가 있습니다. 이 문자들은 m개의 스택으로 배열되고 스택 i에는 문자 스택[i]이 있습니다. 우리의 임무는 다음과 같은 방식으로 모든 스택을 비우는 것입니다.
-
두 개의 스택을 선택하고 둘 다에서 맨 위에 있는 문자를 제거해야 합니다.
-
제거한 문자는 둘 다 같은 번호여야 합니다.
이러한 방식으로 m개의 스택을 비울 수 있으면 true를 인쇄하거나 그렇지 않으면 false를 반환합니다.
따라서 입력이 n =3, m =2, stacks ={{2, 1, 3}, {2, 1, 3}}인 경우 출력은 true가 됩니다.
두 개의 스택이 있으며 각 스택에는 각각 숫자 2, 1, 3이 쓰여진 문자가 있습니다. 따라서 두 스택에서 제거하고 주어진 방식으로 비울 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
Define one 2D array dp
Define an array tvec
for initialize i := 0, when i < m, update (increase i by 1), do:
k := size of stacks[i]
for initialize j := 0, when j < k, update (increase j by 1), do:
if j < 0, then:
insert p at the end of dp[stacks[i, j]]
(increase tvec[p] by 1)
p := stacks[i, j]
Define an array tp
for initialize i := 1, when i <= n, update (increase i by 1), do:
Define one queue q
insert i into q
while (q is not empty), do:
if not tp[first element of q] and tvec[first element of q] is same as 0, then:
for each element next in dp[first element of q], do:
(decrease tvec[next] by 1)
insert next into q
tp[first element of q] := true
delete first element from q
for initialize i := 1, when i <= n, update (increase i by 1), do:
if tvec[i] is not equal to 0, then:
return false
return true 예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, int m, vector<vector<int>> stacks){
vector<vector<int>> dp(n + 1);
vector<int> tvec(n + 1);
for(int i = 0; i < m; i++){
int k = stacks[i].size();
int p;
for(int j = 0; j < k; j++){
if(j > 0){
dp[stacks[i][j]].push_back(p);
tvec[p]++;
}
p = stacks[i][j];
}
}
vector<bool> tp(n + 1);
for(int i = 1; i <= n; i++){
queue<int> q;
q.push(i);
while(!q.empty()){
if(!tp[q.front()] && tvec[q.front()] == 0){
for(auto next: dp[q.front()]){
tvec[next]--;
q.push(next);
}
tp[q.front()]=true;
}
q.pop();
}
}
for(int i = 1; i <= n; i++){
if(tvec[i] != 0){
return false;
}
}
return true;
}
int main() {
int n = 3, m = 2;
vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
cout<< solve(n, m, stacks);
return 0;
} 입력
3, 2, {{2, 1, 3}, {2, 1, 3}} 출력
1