Algoritma Dan Data Struktur

Halo, kali ini saya akan sharing bagaimana menyelesaikan dan mengoptimalkan suatu persoalan sederhana dalam alogritma dan struktur data yaitu Find Max.

Masalah [ Find Max ]

Disuatu sekolah terdapat 34 siswa yang telah melaksanakan ujian semester, lalu ibu x ingin mencoba mencari nilai terbanyak yang muncul dari hasil yang ujian ke 34 siswanya tersebut. Carilah jumlah nilai terbanyak yang muncul dari hasil yang ujian tersebut.

Ketentuan :

• Nilai list/array yang bertipe int.
• Nilai list/array berada pada kisaran 0 - (n-1).
• Niali list/array diberikan tidak berurutan.

Solusi

Cara 1 [BruteForce]

Lakukan Pencarian secara menyeluruh atau dengan teknik Bruteforce, cek setiap elemen dalam list dan cari berapa banyak nilai tersebut muncul dalam list. Pantau terus count dan kemudian cek jika jumlah elemen atau count nya lebih besar dari besar maxCount maka ganti nilai dari maxCount. Gunakan 2x perulangan, perulangan pertama untuk memilih elemen yang ingin di cek dan loop kedua untuk menghitung jumlah kemunculan elemen tersebut.

func FindMaxCount(data []int) int {
	size := len(data)
	max := data[0]
	count := 1
	maxCount := 1
	for  i := 0; i < size; i++ {
		count = 1
		for  j := i + 1; j < size; j++ {
			if data[i] == data[j] {
				count++
			}
		}
		if count > maxCount {
			max = data[i]
			maxCount = max
		}
	}
	return max
}

Dengan Menggunakan cara diatas maka didapatkan :

• Time Complexity = o(n)
• Space Complexity = o(1)

Cara 2 [Urutkan]

Untuk mengunakan cara 2 ini kita harus mengurutkan terlebih dahulu list/array yang diberikan. sehingga kita dapat melakukan hanya sekali perulangan untuk mendapatkan jumlah nilai terbanyak.

func FindMaxCount(data []int) int {
	size := len(data)
	max := data[0]
	maxCount := 1
	curr := data[0]
	currCount := 1
	sort.Ints(data) // Urutkan data
	for  i := 1; i < size; i++ {
		if data[i] == data[i-1] {
			currCount++
		} else {
			currCount = 1
			curr = data[i]
		}
		if currCount > maxCount {
			maxCount = max
			max = curr
		}
	}
	return max
}

Dengan Menggunakan cara diatas maka didapatkan :

• Time Complexity = o(n log n)
• Space Complexity = o(1)

Cara 3 [Menghitung]

Cara ini hanya bisa dilakukan ketika kita mengetahui jangkuan nilai dari nilai yang diberikan. Jika telah mengetahui nilai elemen berada pada jangkuan 0 - (n-1) maka kita dapat membuat suatu list/array baru yang memiliki panjang yang sama dengan jangkuannya. Lalu kita hanya perlu melakukan sekali perulangan untuk mendapatkan nilai yang sering muncul.

Jika nilai jangkuan atau range dari suatu list/array telah diketahui maka itu adalah cara tercepat mendapatkan nilai yang sering muncul dalam suatu list/array.

func FindMaxCount(data []int, rangeOfData int) int {
	size := len(data)
	max := data[0]
	maxCount := 1
	count := make([]int, r)
	for  i := 1; i < size; i++ {
		count[data[i]]++
		if count[data[i]] > maxCount {
			maxCount = count[data[i]]
			max = data[i]
		}
	}
	return max
}

Dengan Menggunakan cara diatas maka didapatkan :

• Menambah nilai count = Time Complexity O (1)
• Membuat membuat list/array dari count = Space Complexity o(n)
• Total Time Complexity = o(n)

Penutup

Sekian sharing saya kali ini, jika ada salah kata maupun penjelasannya masih kurang baik mohon dimaafkan.