পাইথনে প্রাণীদের চূড়ান্ত অবস্থান নির্ণয় যখন সেগুলো থেমে যায়

ধরুন, s একটি স্ট্রিং যা প্রাণীদের প্রাথমিক অবস্থা নির্দেশ করে। প্রতিটি প্রাণী তিনটি মানের একটি হতে পারে: L (বামে চলছে), R (ডানে চলছে), @ (স্থির)। যেসব প্রাণী এক দিকে চলছে সেগুলো অন্যদিক থেকে বল পেলে থেমে যায় এবং @ 상태로 রূপান্তরিত হয়। আমাদের কাজ হল সমস্ত প্রাণী থেমে গেলে তাদের চূড়ান্ত অভিমুখ জানা।

উদাহরণ: s = "@@L@R@@@@L" হলে আউটপুট "LLL@RRRLLL"।

সমাধানের ধাপসমূহ

• levels := s দৈর্ঘ্যের তালিকা -1 দিয়ে পূরণ
• q := ডবল-এন্ডেড কিউ
• s এর প্রতিটি সূচকের জন্য যদি 'R' বা 'L' পাওয়া যায় তবে (idx, 0, dir) কিউতে পুশ করুন
• l := s-এর অক্ষর তালিকা
• যব तक q খালি না হয়:
  • (idx, new_level, dir) := কিউ থেকে পপ
  • যদি levels[idx] == -1 হয়:
    • levels[idx] := new_level; l[idx] := dir
    • যদি dir == 'R' এবং idx+1 < len(l) হয় তবে (idx+1, new_level+1, dir) পুশ করুন
    • অন্যথায় যদি dir == 'L' এবং idx-1 >= 0 হয় তবে (idx-1, new_level+1, dir) পুশ করুন
  • অন্যথায় যদি levels[idx] == new_level হয় এবং l[idx] != dir হয় তবে l[idx] := '@'
• l-এর অক্ষরগুলো জোড়া দিয়ে স্ট্রিং ফেরত দিন

উদাহরণ কোড

from collections import deque
class Solution:
    def solve(self, s):
        levels = [-1 for i in s]
        q = deque()
        for idx in range(len(s)):
            if s[idx] == "R" or s[idx] == "L":
                q.append((idx, 0, s[idx]))
        l = list(s)
        while q:
            idx, new_level, dir = q.popleft()
            if levels[idx] == -1:
                levels[idx] = new_level
                l[idx] = dir
                if dir == "R" and idx + 1 < len(l):
                    q.append((idx + 1, new_level + 1, dir))
                elif dir == "L" and idx - 1 >= 0:
                    q.append((idx - 1, new_level + 1, dir))
            elif levels[idx] == new_level:
                if l[idx] != dir:
                    l[idx] = "@"
        return "".join(l)

ob = Solution()
s = "@@L@R@@@@L"
print(ob.solve(s))

ইনপুট

"@@L@R@@@@L"

আউটপুট

LLL@RRRLLL