07. Array dan vector — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/07/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Bandingkan jalan pikiranmu dengan bagian Cara berpikir, bukan kodenya baris per baris: dua kode yang berbeda bentuk bisa sama-sama benar, dan yang perlu ditiru adalah cara sampai ke sana. Bagian Uji di tiap soal berisi masukan dan keluaran yang sudah diperiksa — jalankan jawabanmu sendiri dengan masukan itu sebelum merasa selesai.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/07/homework/solutions/01-statistik.cpp
./jawab

Soal 1 — Statistik sederhana

Soal. Cetak nilai terkecil, terbesar, dan jumlah dari n bilangan.

Cara berpikir. Ketiga jawaban bisa diperoleh dalam satu kali penelusuran. Nilai awal kecil dan besar diambil dari a[0], bukan dari angka tebakan seperti 0 atau 1000000; dengan begitu data negatif atau data yang sangat besar tetap tertangani.

Penampung jumlah dibuat long long: 100.000 bilangan yang masing-masing sampai 10⁹ menghasilkan 10¹⁴.

Pembahasan.

int kecil = a[0], besar = a[0];
long long total = 0;

for (int i = 0; i < n; i++) {
    if (a[i] < kecil) kecil = a[i];
    if (a[i] > besar) besar = a[i];
    total += a[i];
}

cout << kecil << "\n" << besar << "\n" << total << "\n";

Uji.

Dua baris terakhir adalah kasus tepi yang paling sering meruntuhkan jawaban: array berisi satu elemen (nilai terkecil dan terbesarnya sama), dan data yang seluruhnya negatif (nilai awal besar harus a[0], bukan 0).

Kesalahan umum.

• Memulai besar = 0. Untuk data yang semuanya negatif, jawabannya jadi 0.
• Membaca data ke array tetapi lupa bahwa indeksnya 0 sampai n - 1.

Soal 2 — Membalik urutan

Soal. Cetak isi array dari belakang, tanpa spasi di akhir.

Cara berpikir. Tidak perlu benar-benar membalik isi array; cukup menelusurinya mundur dari n - 1 sampai 0. Urusan spasi diselesaikan seperti di Bab 05: cetak spasi sebelum setiap angka kecuali yang pertama dicetak.

Pembahasan.

for (int i = n - 1; i >= 0; i--) {
    if (i < n - 1) cout << " ";
    cout << a[i];
}
cout << "\n";

Uji.

Kasus n = 1 menguji aturan "tanpa spasi di akhir baris": keluarannya harus satu angka saja, tanpa spasi sesudahnya. Cara paling aman adalah mencetak spasi sebelum setiap angka kecuali yang pertama.

Kesalahan umum.

• Menulis for (int i = n; i >= 0; i--), yang membaca a[n] — di luar batas data.
• Menukar isi array dengan perulangan penuh (i dari 0 sampai n), yang justru mengembalikan urutan semula karena setiap pasangan ditukar dua kali. Kalau memang ingin menukar, batasnya i < n / 2.

Soal 3 — Mencari nilai

Soal. Cetak indeks kemunculan pertama, atau -1.

Cara berpikir. Pola pencarian beruntun: siapkan posisi = -1 sebagai jawaban bila tidak ketemu, telusuri dari depan, dan break pada kecocokan pertama. break itulah yang membuat jawabannya indeks pertama, bukan terakhir.

Pembahasan.

int posisi = -1;
for (int i = 0; i < n; i++) {
    if (a[i] == target) { posisi = i; break; }
}
cout << posisi << "\n";

Uji.

Baris pertama adalah inti soalnya: angka 1 muncul dua kali, dan yang diminta adalah indeks terkecil. Karena itu perulangannya harus break begitu ketemu — tanpa break, jawabannya menjadi kemunculan terakhir.

Kesalahan umum.

• Lupa break, sehingga yang tercetak indeks kemunculan terakhir.
• Mencetak di dalam perulangan, sehingga untuk target yang muncul tiga kali ada tiga baris keluaran.

Soal 4 — Jumlah tiap baris

Soal. Baca matriks b × k, cetak jumlah setiap barisnya.

Cara berpikir. Kuncinya letak penampung: jumlah harus dibuat ulang (bernilai 0) di dalam perulangan baris, bukan di luarnya. Kalau ditaruh di luar, jumlahnya menumpuk dari baris ke baris.

Pembahasan.

for (int i = 0; i < b; i++) {
    long long jumlah = 0;
    for (int j = 0; j < k; j++) jumlah += grid[i][j];
    cout << jumlah << "\n";
}

Uji.

Perhatikan urutan pembacaannya: b dan k dulu, lalu b × k angka dibaca baris demi baris. cin >> tidak peduli pada pindah baris, jadi susunan masukannya boleh berbeda — tetapi urutan angkanya tidak boleh.

Kesalahan umum.

• Menaruh long long jumlah = 0; sebelum perulangan luar.
• Tertukar antara indeks baris dan kolom (grid[j][i]), yang baru ketahuan saat jumlah baris dan kolomnya berbeda.

Tantangan — Saringan Eratosthenes

Soal. Cacah bilangan prima sampai 10⁶ di bawah satu detik.

Cara berpikir. Membalik cara berpikir soal Bab 06: alih-alih bertanya "apakah bilangan ini prima?" satu per satu, tandai sekaligus semua kelipatan setiap bilangan prima yang ditemukan.

Dua detail yang membuatnya cepat dan benar:

• Perulangan luar cukup sampai i * i <= n. Bilangan tersusun mana pun pasti punya faktor yang tidak melebihi akar n, jadi di atas itu tidak ada yang perlu dicoret lagi.
• Perulangan dalam dimulai dari i * i, bukan 2 * i. Kelipatan yang lebih kecil (2i, 3i, …) sudah dicoret oleh bilangan prima yang lebih kecil.

Tulis (long long)i * i <= n agar perkaliannya tidak meluap saat i mendekati akar dari batas int.

Pembahasan.

coret[0] = true;
if (n >= 1) 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;
    }
}

int banyak = 0;
for (int i = 2; i <= n; i++) if (!coret[i]) banyak++;
cout << banyak << "\n";

Periksa: n = 1000000 memberi 78498, n = 2 memberi 1, n = 1 memberi 0.

Uji.

Baris terakhir sekaligus menguji kecepatan. Memeriksa setiap bilangan satu per satu dengan cara akar memerlukan sekitar 67,7 juta langkah, sedangkan saringan hanya beberapa juta — pada pengukuran, 0,108 detik berbanding 0,001 detik, sekitar tujuh puluh kali lebih cepat.

Kesalahan umum.

• Menaruh array bool coret[1000001] di dalam main. Array sebesar itu di memori tumpukan membuat program berhenti mendadak; letakkan sebagai variabel global.
• Lupa mencoret 0 dan 1, sehingga cacahnya bertambah dua.
• Memakai perulangan dalam yang dimulai dari 2 * i. Hasilnya tetap benar, hanya lebih lambat.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/07/osn/solutions/.

Soal 1 — Modus Nilai

Cara berpikir. Cara langsung — untuk setiap nilai, hitung ada berapa yang sama — memerlukan N² = 4 × 10¹⁰ perbandingan. Tidak mungkin.

Petunjuknya ada di batasan: nilainya hanya 1 sampai 1000, jauh lebih sedikit daripada 200.000 data. Jadi yang dibuat bukan array data, melainkan array pencacah sepanjang 1001. Setiap bilangan yang dibaca menambah satu pada kotaknya sendiri, dan seluruh datanya cukup dibaca satu kali.

Syarat "kalau seri pilih yang terkecil" tidak memerlukan kode tambahan: kalau pencarian maksimum berjalan dari indeks kecil ke besar dan memakai > (bukan >=), nilai terkecil yang mencapai frekuensi tertinggi tidak akan pernah tergeser.

Pembahasan.

const int BATAS = 1000;

int n;
cin >> n;

int cacah[BATAS + 1] = {0};
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cacah[x]++;
}

int nilai = 1;
for (int v = 1; v <= BATAS; v++) {
    if (cacah[v] > cacah[nilai]) nilai = v;
}

cout << nilai << " " << cacah[nilai] << "\n";

Datanya sendiri tidak pernah disimpan. Ini pola yang sering muncul: kalau yang ditanya hanya ringkasannya, data mentahnya tidak perlu ditahan di memori.

Uji.

Kesalahan umum.

• Membuat array cacah[1000], sehingga cacah[1000] berada di luar batas. Array sepanjang nilai maksimum selalu berukuran maksimum + 1.
• Memakai >= saat mencari maksimum, sehingga yang menang justru nilai terbesar ketika seri.
• Menyimpan seluruh data ke array int a[200000] lalu memeriksanya berpasangan. Benar, tetapi terlalu lambat.

Soal 2 — Selisih Terkecil

Cara berpikir. Memeriksa semua pasangan memerlukan N² / 2 = 2 × 10¹⁰ perbandingan — terlalu banyak.

Kuncinya satu kalimat: setelah diurutkan, pasangan dengan selisih terkecil pasti bersebelahan. Alasannya, kalau dua bilangan tidak bersebelahan, maka ada bilangan lain di antaranya, dan bilangan itu pasti lebih dekat ke salah satu dari keduanya. Jadi cukup mengurutkan lalu memeriksa N − 1 pasangan bersebelahan.

Biayanya menjadi N log N untuk pengurutan ditambah N untuk pemeriksaan.

Pembahasan.

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

sort(a.begin(), a.end());

long long terkecil = a[1] - a[0];
for (int i = 2; i < n; i++) {
    long long selisih = a[i] - a[i - 1];
    if (selisih < terkecil) terkecil = selisih;
}

cout << terkecil << "\n";

Karena datanya sudah urut naik, a[i] - a[i-1] selalu tidak negatif — tidak perlu nilai mutlak. Penampung awalnya diisi selisih pasangan pertama, bukan angka besar yang dikarang: soal menjamin N ≥ 2, jadi pasangan itu pasti ada.

Uji.

Baris kedua memeriksa data kembar, baris ketiga memeriksa tipe: selisihnya 2 × 10¹⁸, yang masih muat di long long tetapi jauh melewati int.

Kesalahan umum.

• Memakai int untuk data atau untuk selisihnya.
• Mengisi penampung awal dengan angka seperti 1000000000, yang lebih kecil daripada selisih terbesar yang mungkin, sehingga jawabannya salah pada data besar.
• Lupa mengurutkan, lalu memeriksa pasangan bersebelahan pada urutan asli.

Soal 3 — Baris dan Kolom Terbesar

Cara berpikir. Tidak perlu menyimpan seluruh tabel. Saat sebuah angka dibaca, sudah diketahui ia milik baris i dan kolom j, jadi angka itu bisa langsung ditambahkan ke dua penampung: jumlahBaris[i] dan jumlahKolom[j]. Satu kali baca sudah cukup untuk keduanya.

Besarnya jumlah perlu diperiksa: 500 angka bernilai 10⁶ berjumlah 5 × 10⁸, yang masih muat di int, tetapi long long menghilangkan keraguan tanpa biaya berarti.

Nomor baris dan kolom dicetak mulai dari 1, sedangkan indeks array mulai dari 0 — karena itu hasilnya ditambah satu di akhir.

Pembahasan.

vector<long long> jumlahBaris(r, 0), jumlahKolom(c, 0);

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        int x;
        cin >> x;
        jumlahBaris[i] += x;
        jumlahKolom[j] += x;
    }
}

int baris = 0;
for (int i = 1; i < r; i++) {
    if (jumlahBaris[i] > jumlahBaris[baris]) baris = i;
}

int kolom = 0;
for (int j = 1; j < c; j++) {
    if (jumlahKolom[j] > jumlahKolom[kolom]) kolom = j;
}

cout << baris + 1 << " " << kolom + 1 << "\n";

Uji.

Kesalahan umum.

• Mencetak indeks array apa adanya, sehingga jawabannya kurang satu.
• Menyiapkan vector<long long> jumlahKolom(r) — panjangnya harus c, bukan r. Kesalahan ini tidak terlihat pada tabel persegi.
• Memakai >= saat mencari maksimum, sehingga yang menang nomor terbesar.

Kalau masih tersendat

• Program berhenti mendadak pada data besar → Bab 07, peringatan tentang indeks di luar batas dan array lokal yang terlalu besar.
• Jawaban salah hanya untuk data negatif → Bab 07, bagian Pola dasar pada array (nilai awal a[0], bukan 0).
• Perulangan pada vector berjalan tak masuk akal → Bab 07, peringatan tentang v.size() yang tak bertanda.

Sebelum lanjut ke Bagian 2, pastikan kamu bisa menulis dari ingatan: membaca n bilangan ke dalam array, mencari nilai terbesar dan terkecil, dan mengurutkan dengan sort.