Reveal Cards In Increasing Order ใน C++

คำอธิบายปัญหา

มีสำรับไพ่ ต้องการจัดลำดับไพ่ทำให้เมื่อเปิดตามกฎ: เปิดไพ่บนสุด → ย้ายไพ่บนสุดใหม่ไปด้านล่าง → ทำซ้ำ จนหมด ไพ่ที่เปิดออกมาจะเรียงจากน้อยไปมาก ต้องการหาลำดับเริ่มต้นของสำรับ

ตัวอย่าง: [17,13,11,2,3,5,7] → [2,13,3,11,5,17,7]

วิธีแก้ปัญหา (จำลองย้อนกลับด้วย Queue)

1. เรียงไพ่จากน้อยไปมาก
2. ใช้ queue เก็บ index ของตำแหน่งในสำรับ
3. สำหรับแต่ละไพ่ในลำดับที่เรียงแล้ว:
4. ดึง index จาก queue → วางไพ่ที่ index นั้น
5. ดึง index ถัดไป → นำกลับเข้า queue (จำลองการย้ายไพ่บนสุดไปด้านล่าง)

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

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << (i+1 < v.size() ? ", " : "");
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        sort(deck.begin(), deck.end());
        int n = deck.size();
        queue<int> q;
        vector<int> ans(n);
        
        for(int i = 0; i < n; i++) q.push(i);
        
        for(int i = 0; i < n; i++) {
            int idx = q.front(); q.pop();
            ans[idx] = deck[i];
            if(!q.empty()) {
                q.push(q.front());
                q.pop();
            }
        }
        return ans;
    }
};

int main() {
    vector<int> v1 = {17,13,11,2,3,5,7};
    Solution ob;
    print_vector(ob.deckRevealedIncreasing(v1));
    return 0;
}

อินพุต

[17,13,11,2,3,5,7]

เอาต์พุต

[2,13,3,11,5,17,7]