07. Array dan vector

Sebagian besar soal OSN memberi sederet data: nilai ujian, tinggi pohon, koordinat, berat barang. Menyimpannya di variabel terpisah jelas tidak mungkin. Array dan vector adalah wadah untuk deretan data seperti itu.

Array

int a[5];              // lima kotak, isinya belum pasti
int b[5] = {3, 1, 4, 1, 5};

cout << b[0] << "\n";  // 3  -- indeks pertama adalah 0
cout << b[4] << "\n";  // 5  -- indeks terakhir adalah panjang - 1
b[2] = 99;

Array adalah n kotak bertipe sama yang berderet rapat di memori. Yang membuatnya cepat: komputer hanya perlu tahu di mana kotak pertama berada, lalu kotak ke-i dicari dengan satu perhitungan — letak awal ditambah i kali ukuran satu kotak. Karena itulah indeks dimulai dari 0: a[0] berarti "nol kotak dari awal".

indeks:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
b:      |  3  |  1  |  4  |  1  |  5  |
        +-----+-----+-----+-----+-----+

Mengambil b[3] memerlukan waktu yang sama dengan mengambil b[0], tidak peduli arraynya berisi lima atau sejuta kotak.

Aturan penting:

• Indeks dimulai dari 0. Array berukuran n punya indeks 0 sampai n - 1.
• Ukurannya harus diketahui saat compile (angka tetap atau const int).
• Membaca atau menulis di luar batas tidak dicegah compiler. Programnya tetap jalan, dengan nilai sampah, atau berhenti mendadak.

Pola membaca n bilangan:

const int MAKS = 100005;
int a[MAKS];

int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

Pola dasar pada array

// jumlah
long long total = 0;
for (int i = 0; i < n; i++) total += a[i];

// terbesar dan terkecil
int besar = a[0], kecil = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] > besar) besar = a[i];
    if (a[i] < kecil) kecil = a[i];
}

// mencacah yang memenuhi syarat
int genap = 0;
for (int i = 0; i < n; i++) if (a[i] % 2 == 0) genap++;

// mencari nilai, simpan posisinya
int posisi = -1;
for (int i = 0; i < n; i++) {
    if (a[i] == target) { posisi = i; break; }
}

Perhatikan pola "terbesar": nilai awalnya a[0], bukan 0. Kalau semua datanya negatif, memulai dari 0 memberi jawaban salah. Karena nilai awalnya sudah a[0], perulangannya mulai dari i = 1 — memeriksa a[0] lagi tidak salah, hanya mubazir.

Keempat pola di atas punya bentuk yang sama: satu penelusuran, satu penampung, satu keputusan per elemen. Jumlah langkahnya O(n), jadi semuanya tetap cepat sampai n jutaan. Begitu sebuah soal menuntut membandingkan setiap elemen dengan setiap elemen lain, barulah pekerjaannya melonjak menjadi n² — dan itu yang dibahas Bab 11.

vector

vector adalah array yang ukurannya bisa berubah saat program berjalan.

#include <vector>

vector<int> v;             // kosong
v.push_back(10);           // tambah di belakang
v.push_back(20);
cout << v.size() << "\n";  // 2
cout << v[0] << "\n";      // 10

vector<int> w(5, 0);       // 5 elemen, semuanya 0
vector<int> u = {3, 1, 4};

Menelusuri isi vector:

for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";

for (int x : v) cout << x << " ";      // bentuk singkat

push_back menambah satu elemen di belakang, dan vector mengurus sendiri pembesaran memorinya. Biayanya rata-rata tetap kecil, jadi menambah sejuta elemen satu per satu tetap cepat.

Gunakan array biasa kalau ukurannya sudah diketahui dari batas soal, dan vector kalau ukurannya baru ketahuan saat berjalan atau kalau perlu dikirim ke fungsi.

Mengurutkan

sort dari pustaka <algorithm> mengurutkan dari kecil ke besar:

#include <algorithm>

sort(a, a + n);                  // array
sort(v.begin(), v.end());        // vector

Untuk urutan menurun:

sort(v.begin(), v.end(), greater<int>());

Dua nilai yang diberikan ke sort adalah awal dan satu sesudah akhir. Jadi sort(a, a + n) mengurutkan a[0] sampai a[n-1], dan sort(a + 2, a + 5) hanya mengurutkan tiga elemen di tengah. Pola "satu sesudah akhir" ini dipakai seluruh pustaka standar C++.

Mengurutkan n data memerlukan sekitar n log n langkah — untuk 100.000 data sekitar 1,7 juta langkah, sangat cepat. Bandingkan dengan mengurutkan sendiri memakai dua perulangan bersarang, yang memerlukan sekitar 5 miliar langkah untuk n yang sama. Di lomba, mengurutkan sendiri hampir tidak pernah benar sebagai pilihan.

Mengurutkan sering mengubah soal yang tampak sulit menjadi mudah: "dua bilangan yang paling mirip" menjadi "dua bilangan bertetangga" (Bab 08), "ambil yang paling untung" menjadi "ambil dari depan" (Bab 12). Banyak soal greedy di Bab 12 memang dimulai dengan satu baris sort.

Array dua dimensi

Untuk tabel atau peta:

int grid[100][100];

for (int i = 0; i < baris; i++)
    for (int j = 0; j < kolom; j++)
        cin >> grid[i][j];

grid[i][j] berarti baris i, kolom j — baris dulu, baru kolom. Urutan ini sumber kebingungan yang sering, karena pada koordinat matematika biasanya x (mendatar) disebut lebih dulu.

            j=0   j=1   j=2
         +-----+-----+-----+
   i=0   |  7  |  2  |  9  |     grid[0][2] bernilai 9
         +-----+-----+-----+
   i=1   |  4  |  1  |  3  |     grid[1][0] bernilai 4
         +-----+-----+-----+

Jumlah pekerjaannya baris × kolom, jadi peta 1000 × 1000 berarti sejuta langkah untuk sekali telusur.

Ukuran array dua dimensi cepat menjadi besar: int grid[1000][1000] sudah memakai sekitar 4 MB, dan int grid[5000][5000] sekitar 100 MB — melebihi batas memori sebagian besar soal. Kalau batas barisnya besar sedangkan kolomnya kecil, tulis grid[100005][5], bukan sebaliknya.

Array sebagai penanda: saringan bilangan prima

Salah satu pemakaian array yang paling sering di OSN: memakainya sebagai daftar penanda. Saringan Eratosthenes mencari semua bilangan prima sampai n dengan mencoret kelipatan setiap bilangan prima.

const int MAKS = 1000001;
bool coret[MAKS];

void saring(int n) {
    coret[0] = coret[1] = true;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (!coret[i]) {
            for (int j = i * i; j <= n; j += i) coret[j] = true;
        }
    }
}

Telusuri untuk n = 30. Mula-mula semua dianggap belum dicoret, lalu:

Perulangan berhenti di i = 6 karena 6 × 6 melewati 30. Yang tersisa persis sepuluh bilangan prima sampai 30.

Dua rinciannya layak diperhatikan. Pencoretan dimulai dari i * i, bukan dari 2 * i, karena kelipatan yang lebih kecil sudah pasti dicoret oleh bilangan prima yang lebih kecil. Dan bilangan yang sudah dicoret dilewati seluruhnya, karena kelipatannya pun sudah tercoret.

Sesudah dijalankan, coret[x] == false berarti x prima. Memeriksa satu per satu dengan cara akar memerlukan sekitar n √n langkah; saringan hanya sekitar n log log n — untuk n = 10⁶, itu perbedaan antara beberapa detik dan beberapa milidetik.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Array pencacah adalah teknik yang paling sering terpakai. Kalau nilai pada soal dibatasi kecil — misalnya 1 sampai 1000 atau 1 sampai 10⁶ — hampir selalu ada penyelesaian yang memakai array sepanjang batas nilai itu, bukan sepanjang banyaknya data. Membaca kalimat "1 ≤ Aᵢ ≤ 1000" sebagai isyarat "buat cacah[1001]" menghemat banyak waktu berpikir.

Batas memori ikut menentukan penyelesaian. Satu int memakan 4 byte, satu long long 8 byte. Dari situ ukuran array bisa dihitung:

Batas memori tertulis di kepala soal. Kalau perhitungannya melewati batas itu, berarti penyelesaian yang dimaksud soal bukan yang menyimpan semuanya.

Array besar dideklarasikan di luar main. Variabel lokal disimpan di stack, yang jauh lebih sempit daripada memori program. int a[10000000]; di dalam main biasanya membuat program berhenti sendiri sebelum baris pertama dijalankan. Deklarasi di luar main memakai memori global, dan sebagai bonus isinya otomatis nol.

Indeks di luar batas tidak selalu langsung terlihat. C++ tidak memeriksa batas array. a[n] pada array berukuran n kadang berjalan mulus di komputer sendiri dan menghasilkan Runtime Error atau jawaban aneh di mesin penilai. Kalau jawabanmu benar di rumah tetapi ditolak juri, periksa setiap indeks di perbatasan.

Urutkan dulu kalau soal berbicara tentang "terdekat", "berpasangan", atau "berurutan". Mengurutkan N data memakan sekitar N log N langkah — untuk N = 200.000 itu di bawah empat juta langkah, praktis gratis dibandingkan membandingkan semua pasangan yang memerlukan 2 × 10¹⁰ langkah.

Soal yang menyebut 1 sampai N sering lebih mudah dengan indeks 1. Membuat array berukuran n + 1 dan membiarkan indeks 0 kosong menghilangkan seluruh penyesuaian −1 yang mudah salah. Memori yang terbuang satu elemen.

Ringkasan

• Array menyimpan n nilai bertipe sama secara berderet; indeksnya 0 sampai n - 1, dan mengaksesnya selalu sama cepat.
• Menyentuh indeks di luar batas tidak dicegah compiler dan merupakan penyebab Runtime Error yang paling sering.
• Array besar dibuat global dengan ukuran sedikit di atas batas soal.
• vector dipakai bila ukurannya baru diketahui saat berjalan; v.size() bertipe tak bertanda, jadi beri (int) sebelum dikurangi.
• sort bekerja pada rentang awal sampai satu sesudah akhir, memerlukan sekitar n log n langkah, dan sering mengubah soal sulit menjadi mudah.
• Array dua dimensi diakses grid[baris][kolom]; ukurannya cepat menghabiskan memori.
• Array penanda (bool) adalah alat serbaguna; saringan Eratosthenes adalah contoh terpentingnya.

Latihan bergaya OSN

Ketiga soal berikut adalah tiga teknik array yang paling sering muncul di OSN: array pencacah, pengurutan, dan penjumlahan pada array dua dimensi.

Kerangka ketiganya ada di exercises/07/osn/.

Soal 1 — Modus Nilai

Panitia mengumpulkan nilai ujian N siswa. Tentukan nilai yang paling sering muncul beserta banyak kemunculannya. Kalau ada lebih dari satu nilai dengan kemunculan terbanyak yang sama, pilih nilai yang terkecil.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat A₁ A₂ … A_N.

Format keluaran. Satu baris berisi dua bilangan bulat: nilai yang paling sering muncul, lalu banyak kemunculannya.

Batasan.

• 1 ≤ N ≤ 200.000
• 1 ≤ Aᵢ ≤ 1000

Contoh masukan

7
3 1 3 2 1 3 2

Contoh keluaran

3 3

Penjelasan. Nilai 3 muncul tiga kali, nilai 1 dan 2 masing-masing dua kali. Perhatikan batasan Aᵢ ≤ 1000: nilainya jauh lebih sedikit daripada datanya, dan itulah petunjuk cara menyelesaikannya.

Kerangkanya: exercises/07/osn/01-modus-nilai.cpp

Soal 2 — Selisih Terkecil

Diberikan N bilangan bulat. Tentukan selisih terkecil yang mungkin antara dua bilangan pada posisi yang berbeda. Selisih selalu dihitung sebagai bilangan tidak negatif.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat.

Format keluaran. Satu baris berisi selisih terkecil.

Batasan.

• 2 ≤ N ≤ 200.000
• −10¹⁸ ≤ Aᵢ ≤ 10¹⁸

Contoh masukan

5
10 2 7 3 9

Contoh keluaran

1

Penjelasan. Pasangan (2, 3) dan pasangan (9, 10) sama-sama berselisih 1, dan tidak ada pasangan yang lebih dekat. Kalau ada dua bilangan yang sama persis, jawabannya 0.

Kerangkanya: exercises/07/osn/02-selisih-terkecil.cpp

Soal 3 — Baris dan Kolom Terbesar

Sebuah tabel berukuran R baris dan C kolom berisi bilangan bulat. Tentukan nomor baris yang jumlah isinya terbesar dan nomor kolom yang jumlah isinya terbesar. Baris dan kolom dinomori mulai dari 1. Kalau ada seri, pilih nomor yang terkecil.

Format masukan. Baris pertama berisi dua bilangan bulat R dan C. R baris berikutnya masing-masing berisi C bilangan bulat.

Format keluaran. Satu baris berisi dua bilangan bulat: nomor baris dan nomor kolom, dipisahkan satu spasi.

Batasan.

• 1 ≤ R, C ≤ 500
• −10⁶ ≤ isi tabel ≤ 10⁶

Contoh masukan

2 3
1 2 3
4 5 6

Contoh keluaran

2 3

Penjelasan. Jumlah baris pertama 1 + 2 + 3 = 6, baris kedua 4 + 5 + 6 = 15, jadi baris terbesar adalah baris 2. Jumlah kolomnya berturut-turut 5, 7, dan 9, jadi kolom terbesar adalah kolom 3.

Kerangkanya: exercises/07/osn/03-baris-kolom-terbesar.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.