I attempted the following question on codeforces:
https://codeforces.com/problemset/problem/49/D
Below is my code:
int main(){
int n,answer=0;
cin>>n;
string l;
cin>>l;
stack<char> s;
for(int i=0; i <n; i ++){
if(s.size()==0) s.push(l[i]);
else {
if(s.top()!=l[i]) s.push(l[i]);
else {
s.pop();
++answer;
}
}
}
cout<<answer<<"\n";
}
I made a stack and kept pushing the elements of the string. But when the top most element is equal to the element being pushed, i'm popping the top element (Because I can combine those two and create the sequence either 01 or 10 according to the minimal case). The number of times I popped an element is the answer (the number of times I converted 11 or 00 to either 10 or 01 which is the number of steps).
Can anyone help to prove the code?
Aucun commentaire:
Enregistrer un commentaire