Kumpulan Soal Problem Solving C++
Oktober 2024
Daftar Isi
1. Shopping Cart Calculator
2. Matrix Rotation
3. String Encoder
4. Binary Tree Height
5. Balanced Brackets
Soal 1: Shopping Cart Calculator
Deskripsi
Buatlah program untuk menghitung total belanja dari sebuah keranjang belanja
dengan ketentuan: 1. Setiap item memiliki nama, harga, dan jumlah 2. Jika
total belanja > 500000, dapat diskon 10% 3. Jika total belanja > 300000, dapat
diskon 5% 4. Jika jumlah item yang sama >= 3, dapat diskon 2% untuk item
tersebut 5. Diskon dapat bertumpuk (stack)
Format Input
• Baris pertama berisi N (jumlah jenis item berbeda)
• N baris berikutnya berisi: nama_item harga jumlah
Format Output
• Total harga sebelum diskon
• Total diskon
• Total harga setelah diskon
Contoh
Input:
3
Buku 50000 3
Pensil 3000 2
Tas 200000 1
Output:
Total sebelum diskon: 359000
Total diskon: 19770
Total setelah diskon: 339230
1
Solusi
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
struct Item {
string nama;
int harga;
int jumlah;
};
class ShoppingCart {
private:
vector<Item> items;
double hitungDiskonItem(const Item& item) {
double diskon = 0;
if ([Link] >= 3) {
diskon = 0.02;
}
return diskon;
}
double hitungDiskonTotal(double total) {
if (total > 500000) return 0.10;
if (total > 300000) return 0.05;
return 0;
}
public:
void tambahItem(const string& nama, int harga, int jumlah) {
items.push_back({nama, harga, jumlah});
}
void hitungTotal() {
double totalSebelumDiskon = 0;
double totalDiskon = 0;
for (const auto& item : items) {
double subtotal = [Link] * [Link];
totalSebelumDiskon += subtotal;
double diskonItem = hitungDiskonItem(item);
2
totalDiskon += subtotal * diskonItem;
}
double diskonTotal = hitungDiskonTotal(totalSebelumDiskon);
totalDiskon += (totalSebelumDiskon - totalDiskon) * diskonTotal;
double totalSetelahDiskon = totalSebelumDiskon - totalDiskon;
cout << fixed << setprecision(0);
cout << "Total sebelum diskon: " << totalSebelumDiskon << endl;
cout << "Total diskon: " << totalDiskon << endl;
cout << "Total setelah diskon: " << totalSetelahDiskon << endl;
}
};
Soal 2: Matrix Rotation
Deskripsi
Buatlah program untuk merotasi matrix NxN sebesar 90 derajat searah jarum
jam.
Format Input
• Baris pertama berisi N (ukuran matrix)
• N baris berikutnya berisi N angka per baris
Format Output
• Matrix hasil rotasi
Contoh
Input:
3
1 2 3
4 5 6
7 8 9
Output:
7 4 1
8 5 2
9 6 3
3
Solusi
class MatrixRotation {
public:
static void rotate(vector<vector<int>>& matrix) {
int n = [Link]();
// Transpose matrix
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// Reverse each row
for(int i = 0; i < n; i++) {
for(int j = 0; j < n/2; j++) {
swap(matrix[i][j], matrix[i][n-1-j]);
}
}
}
};
Soal 3: String Encoder
Deskripsi
Buatlah program untuk mengenkode string dengan aturan: 1. Jika karakter
muncul berurutan, tampilkan jumlah kemunculan diikuti karakternya 2. Jika
hanya muncul sekali, tampilkan karakternya saja 3. Encoding hanya untuk
huruf (a-z, A-Z)
Format Input
• Satu baris string
Format Output
• String hasil encoding
Contoh
Input:
AABBBCCCCDDEEEE
Output:
4
2A3B4C2D4E
Solusi
class StringEncoder {
public:
static string encode(string s) {
string result = "";
int count = 1;
for(int i = 1; i <= [Link](); i++) {
if(i == [Link]() || s[i] != s[i-1]) {
if(count > 1) {
result += to_string(count);
}
result += s[i-1];
count = 1;
} else {
count++;
}
}
return result;
}
};
Soal 4: Binary Tree Height
Deskripsi
Buatlah program untuk menghitung tinggi maksimum dari binary tree. In-
put diberikan dalam format level-order traversal dimana -1 menandakan node
kosong (null).
Format Input
• Baris pertama berisi N (jumlah node)
• N angka yang merepresentasikan node (-1 untuk null)
Format Output
• Tinggi maksimum tree (dimulai dari 1)
Contoh
Input:
5
7
1 2 3 4 5 -1 7
Output:
3
Solusi
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class BinaryTreeHeight {
public:
static TreeNode* buildTree(vector<int>& nodes) {
if([Link]() || nodes[0] == -1) return NULL;
vector<TreeNode*> treeNodes;
TreeNode* root = new TreeNode(nodes[0]);
treeNodes.push_back(root);
for(int i = 0; i < [Link]()/2; i++) {
if(treeNodes[i] == NULL) continue;
int leftIdx = 2*i + 1;
int rightIdx = 2*i + 2;
if(leftIdx < [Link]() && nodes[leftIdx] != -1) {
treeNodes[i]->left = new TreeNode(nodes[leftIdx]);
treeNodes.push_back(treeNodes[i]->left);
} else {
treeNodes.push_back(NULL);
}
if(rightIdx < [Link]() && nodes[rightIdx] != -1) {
treeNodes[i]->right = new TreeNode(nodes[rightIdx]);
treeNodes.push_back(treeNodes[i]->right);
} else {
treeNodes.push_back(NULL);
}
}
return root;
6
}
static int getHeight(TreeNode* root) {
if(root == NULL) return 0;
return 1 + max(getHeight(root->left), getHeight(root->right));
}
};
Soal 5: Balanced Brackets
Deskripsi
Buatlah program untuk mengecek apakah sebuah string yang berisi bracket {},
[], () sudah seimbang (balanced) atau tidak.
Format Input
• Satu baris string yang berisi bracket
Format Output
• “YES” jika balanced
• “NO” jika tidak balanced
Contoh 1
Input:
{[()]}
Output:
YES
Contoh 2
Input:
{[(])}
Output:
NO
Solusi
class BalancedBrackets {
public:
static bool isBalanced(string s) {
7
stack<char> st;
for(char c : s) {
if(c == '(' || c == '{' || c == '[') {
[Link](c);
} else {
if([Link]()) return false;
if(c == ')' && [Link]() != '(') return false;
if(c == '}' && [Link]() != '{') return false;
if(c == ']' && [Link]() != '[') return false;
[Link]();
}
}
return [Link]();
}
};
Catatan Penutup
Setiap soal dirancang untuk menguji pemahaman konsep pemrograman yang
berbeda: 1. Shopping Cart - OOP dan perhitungan matematis 2. Matrix
Rotation - Manipulasi array 2D 3. String Encoder - String processing 4. Binary
Tree Height - Struktur data tree dan rekursi 5. Balanced Brackets - Stack dan
string processing
Untuk setiap soal, pastikan untuk: - Membaca dan memahami semua per-
syaratan dengan cermat - Mempertimbangkan berbagai test case - Mengop-
timalkan solusi untuk efisiensi - Menangani kasus-kasus khusus