PHP ile Kuyruklar: LeetCode 649 – Dota2 Senatosu Çözümü

PHP ile Kuyruklar: LeetCode 649 – Dota2 Senatosu Çözümü

Bu makalede, LeetCode’un 649 numaralı problemi olan “Dota2 Senatosu”nu PHP kullanarak nasıl çözebileceğinizi adım adım açıklayacağız. Problem, iki farklı fraksiyonun senatoda oylama yapmasını ve oylama sonucunda bir fraksiyonun diğerini nasıl yendiğini ele alıyor. Bu problemi çözmek için kuyruk veri yapısının ne kadar etkili olduğunu göreceğiz. Öncelikle problemi anlamak ve daha sonra PHP ile nasıl çözülebileceğini inceleyeceğiz. Ardından, kodumuzun performansını değerlendireceğiz ve olası iyileştirmelerden bahsedeceğiz.

Problem Tanımı: Dota2 Senatosu

Problem şu şekilde özetlenebilir: Senatoda iki fraksiyon var, “radiant” ve “dire”. Her fraksiyonun belirli sayıda üyesi var. Oylama sırası verilen bir dizi ile belirleniyor. Oylama şu şekilde gerçekleşiyor: Sıradaki senatör oy kullanıyor. Eğer senatör “radiant” ise, bir “dire” senatörünü ortadan kaldırıyor. Eğer senatör “dire” ise, bir “radiant” senatörünü ortadan kaldırıyor. Oylama, bir fraksiyonun üyeleri kalmayıncaya kadar devam ediyor. Kazanan fraksiyon, oylama sonunda üyeleri kalan fraksiyondur.

PHP ile Çözüm: Kuyruk Veri Yapısı

Bu problemi çözmek için, her fraksiyon için bir kuyruk (queue) veri yapısı kullanabiliriz. Kuyruklar, FIFO (First-In, First-Out) prensibiyle çalışan veri yapılarıdır. İlk giren eleman, ilk çıkarılan elemandır. Bu, senatörlerin oylama sırasını doğru bir şekilde yönetmemize olanak tanır. Aşağıda, PHP kullanarak yazılmış bir çözüm örneği bulunmaktadır:

enqueue($i);
        } else {
            $dire->enqueue($i);
        }
    }

    while (!$radiant->isEmpty() && !$dire->isEmpty()) {
        $r = $radiant->dequeue();
        $d = $dire->dequeue();

        if ($r < $d) {
            $radiant->enqueue($r + strlen($senate)); // sonraki tura ekle
        } else {
            $dire->enqueue($d + strlen($senate)); // sonraki tura ekle
        }
    }

    return $radiant->isEmpty() ? 'Dire' : 'Radiant';
}

// Örnek kullanım
$senate = "RD";
$winner = predictPartyVictory($senate);
echo "Kazanan: " . $winner . "\n"; // Çıktı: Radiant


?>

Bu kodda, SplQueue sınıfını kullanarak iki kuyruk oluşturuyoruz. Her senatör, kuyruğa ekleniyor. Oylama işlemi, her iki kuyrukta da eleman kalmayıncaya kadar devam ediyor. Sonuç olarak, kazanan fraksiyon belirleniyor.

Performans Analizi ve İyileştirmeler

Bu çözümün zaman karmaşıklığı O(N) olup, N senatör sayısını temsil eder. Bu, oldukça verimli bir çözümdür. Ancak, çok büyük girdiler için performansı daha da iyileştirmek için bazı optimizasyonlar yapılabilir. Örneğin, kuyruk işlemlerini daha verimli hale getirmek için farklı bir veri yapısı kullanılabilir. Ancak bu problem için SplQueue yeterlidir.

Sonuç

Bu makalede, LeetCode 649 problemine PHP kullanarak bir çözüm sunduk. Kuyruk veri yapısının, bu tür problemleri çözmek için ne kadar kullanışlı olduğunu gösterdik. Ayrıca, kodumuzun performansını analiz ettik ve olası iyileştirmelerden bahsettik. Daha fazla PHP ve algoritma problemleri için fatihsoysal.com sitesini ziyaret edebilirsiniz.

#Etiketler: PHP, Kuyruk, Queue, LeetCode, Dota2 Senatosu, Algoritma, Veri Yapısı, Problem Çözme, Programlama, SplQueue, FIFO