แผนการเรียน
/

Day 03: Practice Session
STL Data Structures in Action

6 โจทย์ท้าทายเพื่อฝึกการเลือกใช้ Container

1. Distinct Numbers: การนับเลขที่ไม่ซ้ำ (Set) 2. Balanced Brackets: ตรวจสอบวงเล็บ (Stack) 3. Everywhere Man: นับเมืองที่ไป (Set/Unordered Map) 4. K-th Largest: หาค่าใหญ่ที่สุดลำดับที่ K (Priority Queue) 5. Nearest Element: ค้นหาตัวใกล้เคียง (Set Lower Bound) 6. Two Sum: หาคู่บวก (Map/Unordered Map)

Problem 1: Distinct Numbers

โจทย์: ให้เลข \(N\) ตัว (\(N \le 2 \cdot 10^5\)) จงหาว่ามีเลขที่แตกต่างกันทั้งหมดกี่ตัว?

ระดับ TLE (\(O(N^2)\))

ใช้อาเรย์ปกติ แล้ววนลูปซ้อนลูปเพื่อเช็คว่าเลขตัวนี้เคยนับไปหรือยัง

ระดับ Pass (\(O(N \log N)\))

ใช้ std::set เก็บข้อมูล ข้อมูลที่ซ้ำจะถูกปฏิเสธโดยอัตโนมัติ แล้วตอบ s.size()

Problem 2: Balanced Brackets

// Step-by-Step Solution (Pass Level)

1. สร้าง stack<char> s;
2. วนลูปอ่าน String ทีละตัว:
   - เจอ '(' หรือ '[' ให้ s.push(c);
   - เจอ ')' หรือ ']' ให้เช็ค s.top() ว่าเข้าคู่ไหม
3. ถ้าจบโปรแกรมแล้ว stack ว่าง แสดงว่าสมดุล

การใช้ String Replace วนลูปหาคู่จะทำให้ติด TLE ในกรณีวงเล็บซ้อนกันลึกๆ

Problem 3: I’ve Been Everywhere, Man

นับจำนวนเมืองที่แตกต่างกันที่พนักงานเดินทางไป (ข้อมูลเป็น String)

TLE ERROR: วนลูปเปรียบเทียบ String ใน Vector ทีละตัว (\(O(N^2 \cdot L)\))
PASS: ใช้ std::unordered_set<string> เพื่อการค้นหาเฉลี่ย \(O(1)\)

Problem 4: Top K Elements

รับเลขเข้ามาเรื่อยๆ และต้องหาค่าที่ใหญ่ที่สุด ณ ปัจจุบันเสมอ

TLE:
std::sort ทุกครั้งที่มีเลขใหม่ (\(O(N^2 \log N)\))
PASS:
ใช้ std::priority_queue (\(O(\log N)\) ต่อการเพิ่ม)

Problem 5: Nearest Element in Set

Implementation 

auto it = s.lower_bound(x);
if (it == s.begin()) cout << *it;
else if (it == s.end()) cout << *(--it);
else {
   int a = *it; it--;
   int b = *it;
   if (x-b < a-x) cout << b; else cout << a;
}

ใช้ Binary Search ภายใน Tree (\(O(\log N)\)) แทนการ Linear Scan (\(O(N)\))

Problem 6: Sum of Two Values

หาตำแหน่ง \(i, j\) ที่ \(a_i + a_j = X\) โดย \(N \le 2 \cdot 10^5\)

Brute Force (\(O(N^2)\)): Loop \(i\), Loop \(j\) \(\rightarrow\) TLE แน่นอน
Optimized (\(O(N \log N)\)): วนลูปตัวเดียวแล้วเช็ค map.count(X - a[i])

Checklist เพื่อผ่านระดับ PASS

1. ใช้ ios::sync_with_stdio(0); cin.tie(0); เพื่อ Fast I/O
2. เลือก unordered_map แทน map ถ้าไม่สนลำดับ เพื่อลดจาก \(O(\log N)\) เป็น \(O(1)\)
3. ทำ Up-solving ทันทีที่อ่านเฉลยเข้าใจ เพื่อฝึก Implement จริง