मान लीजिए हमारे पास 'L', 'R' और 0 से 9 तक के अंकों वाली एक स्ट्रिंग S है। मान लें कि 10 कमरों वाला एक होटल है जो बाएं से दाएं 0 से 9 तक संख्यांकित हैं। होटल में दो प्रवेश द्वार हैं - एक बाईं ओर से, और दूसरा दाईं ओर से। जब कोई ग्राहक बाएं प्रवेश द्वार के माध्यम से होटल में आता है, तो उसे बाएं प्रवेश द्वार के सबसे निकट का खाली कमरा मिलता है। इसी तरह, जब कोई ग्राहक दाएं प्रवेश द्वार के माध्यम से होटल में आता है, तो उसे दाएं प्रवेश द्वार के सबसे निकट का खाली कमरा मिलता है। लेकिन हमने कमरा आवंटन सूची खो दी है। लेकिन हमें सभी ग्राहक याद हैं: जब कोई ग्राहक आया, किस प्रवेश द्वार से, और जब उन्होंने होटल छोड़ा। प्रारंभ में होटल खाली था। हमें मेमोरी से कमरा आवंटन सूची पुनर्प्राप्त करनी है। S में, 'L' का अर्थ है कि व्यक्ति बाईं ओर से आया, यदि यह 'R' है तो वह दाईं ओर से आया, और अंक d इंगित करता है कि ग्राहक कमरा 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
