ধরুন আমাদের কাছে 'L', 'R' সহ একটি স্ট্রিং S আছে এবং 0 থেকে 9 পর্যন্ত সংখ্যা রয়েছে। বিবেচনা করুন 10টি রুম সহ একটি হোটেল আছে যেগুলি বাম থেকে ডানে 0 থেকে 9 পর্যন্ত সংখ্যাযুক্ত। হোটেলটির দুটি প্রবেশপথ রয়েছে- একটি বাম দিক থেকে এবং আরেকটি ডান দিক থেকে। যখন একজন গ্রাহক বাম প্রবেশদ্বার দিয়ে হোটেলে পৌঁছান, তখন তারা বাম প্রবেশপথের নিকটতম একটি খালি রুম পান। একইভাবে, যখন একজন গ্রাহক ডান প্রবেশদ্বার দিয়ে হোটেলে পৌঁছান, তখন তারা ডান প্রবেশদ্বারের নিকটতম একটি খালি রুম পান। কিন্তু আমরা রুম অ্যাসাইনমেন্ট তালিকা হারিয়েছি। তবে আমরা সমস্ত গ্রাহকদের মনে রাখি:কখন একজন গ্রাহক এসেছেন, কোন প্রবেশদ্বার থেকে এবং কখন তারা হোটেল ছেড়েছেন। প্রথমে হোটেলটি খালি ছিল। আমাদের মেমরি থেকে রুম অ্যাসাইনমেন্টের তালিকা পুনরুদ্ধার করতে হবে। S-তে, 'L' মানে ব্যক্তিটি বাম দিক থেকে এসেছে, যদি এটি 'R' হয় তবে সে ডান দিক থেকে এসেছে, এবং d সংখ্যাটি নির্দেশ করে যে গ্রাহক ঘর ছেড়ে চলে গেছে। আমাদের রুমের অবস্থা ফেরত দিতে হবে। একটি স্ট্রিং যার দৈর্ঘ্য 10 এবং এটি 0, মানে রুম খালি, অন্যথায় এটি দখল করা হয়৷
সুতরাং, যদি ইনপুটটি S ="LLRL1RL1" এর মত হয়, তাহলে আউটপুট হবে "1010000011", কারণ
প্রথমত, সব কক্ষ খালি। স্থিতি 0000000000।
L - গ্রাহক বাম প্রবেশপথ দিয়ে হোটেলে পৌঁছান। স্ট্যাটাস 1000000000।
L - বাম প্রবেশদ্বার থেকে গ্রাহক। স্ট্যাটাস 1100000000।
R - ডান প্রবেশদ্বার থেকে গ্রাহক। স্ট্যাটাস 1100000001।
L - বাম প্রবেশদ্বার থেকে গ্রাহক। স্ট্যাটাস 1110000001।
1 - কাস্টমার 1 রুমে চলে যায়। স্ট্যাটাস 1010000001।
R - ডান প্রবেশদ্বার থেকে গ্রাহক। স্ট্যাটাস 1010000011।
L - বাম প্রবেশদ্বার থেকে গ্রাহক। স্ট্যাটাস 1110000011।
1 - কাস্টমার 1 রুমে চলে যায়। স্ট্যাটাস 1010000011।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := size of S a := "0000000000" for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is same as 'L', then: set left most 0 in a to 1 if S[i] is same as 'R', then: set right most 0 in a to 1 Otherwise set S[i]th place in a to 0 return a
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
string solve(string S) {
int n = S.size();
string a = "0000000000";
for (int i = 0; i < n; i++) {
if (S[i] == 'L')
a[a.find('0')] = '1';
if (S[i] == 'R')
a[a.rfind('0')] = '1';
else
a[S[i] - '0'] = '0';
}
return a;
}
int main() {
string S = "LLRL1RL1";
cout << solve(S) << endl;
} ইনপুট
"LLRL1RL1"
আউটপুট
1010000011
