Algoritma Soruları ve Çözümleri – Örnek 1

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Algoritma Eğitimlerinde Search ve Sort Algoritmalarından sonra Örnek Algoritma Soruları ve Çözümleri ile öğrendiğimiz Algoritmaları pekiştiriyoruz. Bu dersimizde örnek bir soru paylaşıp çözümünü yapmaya çalışacağız.

Öncelikle sorunun orijinaline bu linkten ulaşabilirsiniz. Yazdığınız çözüm kodunu göndermek için siteye üye olmanız gerekiyor. Email aktivasyonunu tamamladıktan sonra soru sayfasının sağ alt kısmında bulunan “Submit” bölümünü kullanarak istediğiniz yazılım dilini seçiyorsunuz. Daha sonra yazdığınız kodu gönderip test edebilirsiniz. Nice Accepted‘lar görmeniz dileğiyle…

Algoritma Soruları

Örnek 1:

Size ilk satırda N ve M değerleri veriliyor. Sonra gelen 2 satırda N uzunluğunda A dizisi ve M uzunluğunda B dizisi veriliyor. Bizden istenen her bir B[i] elemanı için A dizisinde kaç eleman vardır ki B[i]‘den küçük eşit olsun.

Girdiler:

N,M, A dizisi, B dizisi.

Çıktı:

Her bir B[i] elemanı için şartları sağlayan eleman sayısı.

Sınırlamalar:

1 ≤ N, M ≤ 2·10^5

-10^9 ≤ A[i] ≤ 10^9

-10^9 ≤ B[i] ≤ 10^9

Örnek Girdi 1:

5 4
1 3 5 7 9
6 4 2 8

Örnek Çıktı 1:

3 2 1 4

Örnek Girdi 2:

5 5
1 2 1 2 5
3 1 4 1 5

Örnek Çıktı 2:

4 2 4 2 5

Örnek Girdi 1 Açıklaması:

6 elemanından küçük olanlar: 1,3,5 yani 3 eleman.

4 elemanından küçük olanlar: 1,3 -> 2 eleman.

2’den küçükler 1 -> 1 eleman.

8’den küçükler 1,3,5,7 -> 4 eleman

Yani cevap: 3,2,1,4 olacaktır.

Soruyu biraz düşündükten sonra çözüme bakmanız sizin için daha yararlı olacaktır.

Çözüme geçmeden önce ufak bir tüyo verelim: Binary Search. Belki bu çözümü bulmanıza yardımcı olabilir.

Çözüm:

Öncelikle bize verilen A dizisinin sıralamasının bir önemi yoktur. Biz her seferinde A dizisinde bir eleman arayacağımız için önce A dizisini sıralamalıyız. A dizisini sıraladık. Şimdi B dizisindeki her eleman için A’da nereye denk geleceğini bulsak başlangıç ile o eleman arasındaki bütün değerler bizim cevabımızda olmalıdır. Akla ilk gelen yöntem B’deki her eleman için A dizisinde for döngüsü açıp küçük bütün elemanları saymaktır. Ancak ne yazık ki bu zaman sınırlamalarını oldukça aşıyor. Bunu da şöyle hesaplayalım. A dizisinin uzunluğu maksimum 100 000 olabilir. B dizisinin uzunluğu da 100 000 olabilir. Böyle bir durumda her B[i] için en kötü ihtimalde bütün A dizisi gezileceği için karmaşıklık 10^5 * 10^5 = 10^10 (10 000 000 000) olacaktır ilk yazılarımızda bahsetmiştik böyle algoritmik sorularda süre sınırlaması 2 saniyedir. Yani en fazla 200 000 000 işlem yapabiliriz.

Bunun önüne geçmek için Binary Search algoritmasını kullanacağız. Her B[i] elemanının A dizisindeki yerini bulmak için A dizisinde Binary Search ile B[i] elemanını arayacağız. Aradık ve A[x] noktası B[i]’den büyük olmayan ilk eleman olduğunu varsayalım. Bu durumda B[i] için cevap x olacaktır. Çünkü x’den sonraki hiç bir eleman B[i]’den büyük olmamakla birlikte 1 ile x arasındaki bütün elemanlar B[i]’den küçük eşittir.

Bu işlemi her B elemanı için yaptığımızda karmaşıklığımız 10^5 * log2(10^5) = 1 660 964 olacaktır. Bu işlem de 2 saniye süre kısıtlamasında çok rahat kurtaracaktır.

Çözüm Kodu:

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

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
 
    
    int L[n1], R[n2];
 
    
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
 
    
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        
        int m = l+(r-l)/2;
 
        
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
 
        merge(arr, l, m, r);
    }
}
int BinarySearch(int dizi[], int bas, int son, int deger){
    if(son >= bas){
        int orta = (bas + son)/2;
        
        if(dizi[orta] > deger)
            return BinarySearch(dizi, bas, orta-1, deger);
 
    else return BinarySearch(dizi, orta+1, son, deger);
   }
 
 return bas-1;
}
int n,m,A[200005],B[200005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
	scanf("%d",&A[i]);   
 
    for(int i=1;i<=m;i++)
	scanf("%d",&B[i]);

    mergeSort(A,1,n);
    
    for(int i=1;i<=m;i++){
        printf("%d ",BinarySearch(A,1,n,B[i]));
    }

}

Okuduğunuz için teşekkürler umarım faydalı olmuşumdur. İstediğiniz başka soru çözümleri olursa yorumlarda belirtebilirsiniz. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bundan sonra örnek Algoritma soruları paylaşıp yukarıdaki gibi çözümlerini paylaşmaya çalışacağız. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.