หาการจัดคิวหลังเวลา T ในปัญหา M/F Queue ใน C++

ในปัญหานี้ เราได้รับ string ของ 'M' (Male) และ 'F' (Female) และเวลา T ผู้ชายจะสลับตำแหน่งกับผู้หญิงที่อยู่ด้านหลังทุก 1 หน่วยเวลา

ตัวอย่าง

Input: queue = "MFMMFF", t = 3 Output: FFMFMM

T=0: MFMMFF → T=1: FMMFMF → T=2: FMFMFM → T=3: FFMFMM

วิธีการแก้ปัญหา: Simulation O(N×T)

วน T รอบ, แต่ละรอบสแกนซ้ายไปขวา หา "MF" แล้ว swap เป็น "FM" (ข้ามตัวถัดไปเพื่อไม่ swap ซ้ำในรอบเดียวกัน)

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

string rearrangeQueue(string queue, int t) {
    int n = queue.length();
    for (int time = 0; time < t; time++) {
        for (int i = 0; i < n - 1; i++) {
            if (queue[i] == 'M' && queue[i+1] == 'F') {
                swap(queue[i], queue[i+1]);
                i++; // skip next position
            }
        }
    }
    return queue;
}

int main() {
    cout << rearrangeQueue("MFMMFF", 3); // FFMFMM
    return 0;
}

ผลลัพธ์

FFMFMM

หมายเหตุ: สำหรับ T ใหญ่ๆ สามารถ optimize ด้วยการคำนวณตำแหน่งสุดท้ายโดยตรงได้ (แต่ซับซ้อนกว่า)