บทความ เข้าสู่เนื้อหา คอร์สลงมือทำ
Data Structures and Algorithms Fundamentals

Data Structures คืออะไร?

5

Introduction

เชื่อว่าในหลาย ๆ ครั้งเวลาที่เราได้ยินคำว่า algorithm อีกคำศัพท์นึงที่เรามักจะได้ยิน ซึ่งมักจะติดกันมาเป็นแพคคู่เลย ก็คือคำว่า ‘Data Structure’

แล้ว data structure คืออะไร? เกี่ยวข้องอะไรกับคำว่า algorithm? ทำไมถึงสำคัญ? เราจะเอาไปใช้แก้ปัญหาในงานที่เราทำได้อย่างไร? เชื่อว่าทุกคนน่าจะมีคำถามแบบนี้แน่นอน แต่ก่อนที่จะไปเริ่มต้นตอบคำถามเหล่านี้กัน เช่นเคย เรามาลองดูตัวอย่างปัญหาง่าย ๆ กันก่อนดีกว่า

Library of Alexandria

“ณ​ ห้องสมุดแห่งหนึ่งซึ่งมีหนังสือประมาณ 100,000 เล่ม ในแต่ละวันจะมีคนมายืมหนังสือทั้งหมด 1,000 เล่มและคืนหนังสือทั้งหมด 100 เล่ม”

ถ้าหากว่าคุณเป็นคนที่ได้รับมอบหมายให้เป็นคนออกแบบห้องสมุดแห่งนี้ คุณจะออกแบบห้องสมุดอย่างไรให้ผู้ใช้งานมีประสบการณ์การใช้งานที่ดีที่สุด (ในแง่ของการหา การยืม และการคืนหนังสือ)

โดยกำหนดให้ 1 operation ใด ๆ ก็ตามใช้เวลาประมาณ 0.5 วินาที

ห้องสมุด v1

เราอาจจะเริ่มจากอะไรที่มันง่ายที่สุดก่อน (แล้วถ้ามีปัญหาอะไรค่อยลองปรับหาวิธีแก้ทีหลัง) โดยเราอาจจะนำหนังสือทั้งหมดมาวางเรียงต่อกันเป็นแถว แบบปน ๆ กันไป

A list of books

สำหรับวิธีนี้แน่นอนว่าถ้าหากผู้ใช้งานต้องการจะหาหนังสือสักเล่ม ก็ต้องเดินไล่หาทั้งหมดอย่างมากเท่ากับจำนวนหนังสือทั้งหมดหรือประมาณ 100,000 ครั้งเลยทีเดียว (ประมาณ 50,000 วินาทีหรือเกือบ ๆ 14 ชั่วโมง) แต่ในทางตรงกันข้าม การคืนหนังสือก็สามารถคืนได้ทันที เนื่องจากเราสามารถวางไว้หลังสุดของแถวหนังสือได้เลยนั่นเอง (ใช้เวลา 0.5 วินาที)

ส่วนการยืมหนังสือนั้น ก็คือการหยิบการหนังสือเล่มหนึ่งออกมาจากแถวหนังสือ พอเราหยิบหนังสือออกมาแล้วเราก็อาจจะต้องจัดเรียงแถวใหม่ โดยการเลื่อนหนังสือทั้งหมดด้านหลังหนังสือที่หยิบออกมาให้มาชิดกัน (shift)

Book borrowing or deletion

โดยสรุปแล้ว: การหาหนังสือ \(O(n)\), การยืมหนังสือ \(O(n)\), การคืนหนังสือ \(O(1)\)

สำหรับวิธีนี้จะเห็นว่าการคืนหนังสือจะทำได้เร็วมาก ๆ ในขณะที่การหาหนังสือทำได้ช้าสุด ๆ ซึ่งถ้าดูจากปัญหาเราก็จะพบว่าใน 1 วันจะมีคนมาหาหนังสือและยืมหนังสือกว่า 1,000 เล่ม ในขณะที่คนมาคืนหนังสือแค่ 100 เล่มเท่านั้น

สำหรับแถวหนังสือในห้องสมุด v1 นั้น เปรียบเหมือน array ที่ไม่มีการเรียงลำดับ การคืนหนังสือก็คือ push ข้อมูลใหม่เข้าไปท้ายสุดของ array; ส่วนการยืมนั้นคือการ deletion ดังนั้นพอนำค่าที่จะลบออกไปแล้วเราต้อง shift element ด้านหลังตัวที่ลบทั้งหมดไปด้านหน้า 1 ตำแหน่ง

อีกวิธีการหนึ่งในการเก็บข้อมูลคือการใช้ linked list โดยสำหรับ linked list นั้นการหาหนังสือและการคืนจะใช้เวลาเท่ากับ array เลย แต่สำหรับการลบนั้นจะเป็น O(1) (ไม่รวมการ traverse ไปที่ node นั้นซึ่งเป็น O(n)) เนื่องจากเราแค่แก้ pointer ของ node ก่อนหน้าไปยัง node ด้านหลัง node ที่จะลบได้เลย (อ่านเพิ่มเติมในหัวข้อ ‘Linked List’)

ห้องสมุด v2

สมมุติว่าวันหนึ่ง ทีมของคุณได้ไปเก็บข้อมูลการใช้งานห้องสมุดมาแล้วพบว่า “โดยเฉลี่ยแล้ว ผู้ใช้งานจะเลือกหาหนังสือเพื่อมาลองอ่านประมาณ 10 เล่ม ก่อนที่จะตัดสินใจยืมเล่มใดเล่มหนึ่ง”

จากข้อมูลตรงนี้เราจะเห็นว่าความเร็วในการหาหนังสือเป็นอะไรที่สำคัญมาก ซึ่งถ้าอ้างอิงจากห้องสมุด v1 ถ้าหากว่าเราจะต้องหาหนังสือ 10 เล่ม เราอาจจะต้องใช้เวลาเท่ากับ 500,000 วินาทีหรือประมาณเกือบ 6 วันเลยทีเดียว!

10∗100,000 books∗0.5s=500,000s10 * 100,000 \text{ books} * 0.5s = 500,000s

หนึ่งวิธีที่เราสามารถทำได้คือ “ปรับเปลี่ยนวิธีการจัดเก็บข้อมูล” ครับ

แทนที่เราจะเอาหนังสือมาวางเรียงกันมั่ว ๆ ทำไมเราไม่เรียงตามตัวอักษรจากมากไปน้อยหละ!? ส่วนสำหรับการหาหนังสือนั้น ในเมื่อหนังสือมันเรียงกันอยู่แล้ว เราก็สามารถ Binary Search ตรง ๆ ได้เลย; โดยหนังสือทั้งหมด 100,000 เล่มนั้น จะใช้จำนวน operation ในการหาอย่างมาก 17 ครั้ง หรือไม่เกิน 8.5 วินาทีเท่านั้น

โดยสรุปแล้ว: การหาหนังสือ \(O(log_2n)\), ส่วนการยืมหนังสือนั้นใช้เวลาเท่าเดิมก็คือ \(O(n)\) เพราะหลังจากหยิบหนังสือออกมาแล้วเราต้อง shift หนังสือด้านหลังไปด้านหน้า 1 หน่วย

ห้องสมุด v3

ตอนนี้ประสบการณ์การใช้งานห้องสมุด v2 ของเราเริ่มดีขึ้นแล้ว การหาหนังสือต่อเล่มใช้เวลาเพียงแค่ 8.5 วินาที แต่สำหรับการยืมและการคืนหนังสือนั้นค่อนข้างที่จะใช้เวลานานอยู่ คำถามก็คือเราสามารถพัฒนาการยืมและการคืนให้เร็วกว่านี้ได้ไหม

แน่นอนว่าได้ครับ และหนึ่งวิธีที่เราสามารถทำได้คือ “ปรับเปลี่ยนวิธีการจัดเก็บข้อมูล” นั่นเอง

วิธีการหนึ่งที่เราสามารถทำได้ก็คือการแบ่งโซนตามหมวดหมู่ (จัดเรียงหนังสือตาม category); จากเดิมที่มีหนังสือแค่กองเดียว ตอนนี้ก็มีหลายกองขึ้นอยู่กับจำนวน category

สมมุติว่าถ้าหากมี 8 category นั่นก็หมายความว่าจากเดิมที่เราจะต้องจัดการ operation ต่าง ๆ บนหนังสือทั้งหมด ตอนนี้เราจัดการ operation ต่าง ๆ บนหนังสือแค่ n/8 เล่มเท่านั้น ซึ่งก็หมายความว่าการหา การยืม และการคืนจะทำได้เร็วขึ้นนั่นเอง

Books by genre
โดยหนังสือในแต่ละ category เป็น sorted list of books เหมือน v2

อีกวิธีการหนึ่งที่เราสามารถทำได้เพื่อช่วยลดเวลาในการยืมและคืนหนังสือนั้นก็คือการทำสิ่งที่เรียกว่า ‘Batch Processing’ โดยเราสามารถเก็บงานที่ต้องทำหลาย ๆ งานเอาไว้ก่อน จากนั้นค่อยทำทีเดียวพร้อมกันตอนหลัง ยกตัวอย่างเช่น

เราอาจจะวางตะกร้าเอาไว้สำหรับคืนหนังสือ โดยผู้ใช้งานเวลาจะคืนก็แค่เอาหนังสือมาวางไว้ในตะกร้าดังกล่าว (Time complexity \(O(1)\)) หลังจากนั้นตอนที่เราปิดร้าน เราก็เอาหนังสือในตะกร้าทั้งหมดเข้าไปรวมกับหนังสือที่วางเรียงกันอยู่ในชั้นนั่นเอง

หรือสำหรับการยืมหนังสือนั้นเราอาจจะตั้งกฏเอาไว้ว่า ถ้าใครจะยืมหนังสือเล่มไหนก็ให้เอากล่องเปล่าไปวางแทรกเอาไว้ (Time complexity \(O(1)\)) จากนั้นตอนที่ปิดร้านก็ค่อยเอากล่องเปล่าทั้งหมดออกและจัดเรียงหนังสือในชั้นใหม่ทั้งหมดในครั้งเดียว

ถ้าสรุปห้องสมุด v3 ออกมาเป็นภาพ เราอาจจะสรุปออกมาได้ดังนี้

V3 Summary

จริง ๆ เชื่อว่ามีอีกหลายวิธีเลยที่เราสามารถทำได้ เพื่อให้การหาหนังสือ (Find) การยืมหนังสือ (Deletion) และการคืนหนังสือ (Insertion) ทำได้อย่างมีประสิทธิภาพมากกว่านี้ อยากให้ไปลองคิดต่อเล่น ๆ กันดูนะครับ

Data Structure คืออะไร?

จากตัวอย่างข้างต้นจะเห็นว่า ‘รูปแบบการจัดเก็บข้อมูล’ นั้นส่งผลโดยตรงกับ ‘การจัดการข้อมูล’ (หรือ operation ต่าง ๆ เช่น Find, Insert, Delete) ในชนิดที่ว่าแยกออกจากกันไม่ได้

ซึ่งวิธีการหรือรูปแบบการจัดเก็บข้อมูลที่ว่านี้ ก็คือสิ่งที่เราเรียกกันว่า “Data Structure” นั่นเอง

“A data structure is a way of organizing and storing data in a computer so that it can be accessed and used efficiently.”

แต่แน่นอนว่าไม่มี ‘รูปแบบการจัดเก็บข้อมูล’ ไหนที่สามารถใช้แก้ปัญหาได้ทุกอย่างบนโลกนี้ แต่ละ data structure ย่อมมีสิ่งที่ต้องแลกหรือ trade off ของมัน ยกตัวอย่างเช่น ห้องสมุด v1 เราสามารถคืนหนังสือได้ภายใน \(O(1)\) แต่ในห้องสมุด v2 การคืนใช้ \(O(n)\) เพื่อแลกกับการหาหนังสือที่เร็วขึ้นคือ \(O(log_2n)\)

หรือบาง data structure อาจแลกมาด้วยการใช้ memory เพื่อเก็บข้อมูลมากขึ้น (space-time trade-off) หรืออาจแลกมาด้วยความซับซ้อนในการ implemement ที่เพิ่มมากขึ้น

ดังนั้นใน section นี้เอง เราจะมาลองดูตัวอย่าง data structure ยอดฮิตต่าง ๆ กัน เพื่อให้เราได้เข้าใจ trade-off รวมไปถึง implementation ของแต่ละตัว ก่อนที่เราจะไปจบด้วยการคุยกันว่าเราจะใช้ data structure เหล่านี้ในการแก้ปัญหาได้อย่างไร

Linked List

Linked List

Linked List เป็นโครงสร้างข้อมูลแบบหนึ่งที่มีความเป็น linear โดยเราจะเรียกข้อมูลแต่ละก้อนว่า ‘Node’ และแต่ละ node ก็จะเชื่อมไปหา node ตัวถัดไป; จะเห็นว่าในแต่ละ node เราจะเก็บข้อมูล 2 อย่างก็คือ data และ pointer ที่ชี้ไปหา node ตัวถัดไป

ยกตัวอย่างเช่นระบบ playlist เพลงใน Spotify ที่เมื่อเล่นเพลงหนึ่งอยู่ เราสามารถที่จะกด next ไปหาเพลงถัดไปที่อยู่ติดกันได้ (พอถึงเพลงสุดท้ายก็จะกด next เล่นต่อไม่ได้แล้ว)

บางคนอาจจะถามว่า แล้วถ้าเราเก็บข้อมูลแบบนี้ เราจะเล่นเพลงก่อนหน้าได้ยังไง? คำตอบก็คือ “ก็เก็บ node ก่อนหน้าเอาไว้ด้วยสิ!”

Doubly Linked List

เราเรียก linked list แบบนี้ว่า ‘Doubly Linked List’ ซึ่งจะเก็บข้อมูล 3 อย่างก็คือ previous node, next node, และ node data นั่นเอง

แล้วถ้าหากว่าเราอยากให้ playlist เพลงของเราพอเล่นจบแล้ว กลับมาเล่นเพลงแรกต่อหละ จะทำยังไง? ถึงตอนนี้อาจจะลองคิดเล่น ๆ ดูนะครับว่าเราจะต้องเก็บข้อมูลอะไรเพิ่ม

…

ง่าย ๆ เลยครับ เราก็เก็บ next node ของ node สุดท้ายมาเป็น node แรกสิ ส่วน previous node ของ node แรก ก็ให้ชี้ไปยัง node ตัวสุดท้าย ซึ่งเราจะเรียก linked list แบบนี้ “Circular Linked List” นั่นเอง

Circular Linked List

ส่วนสำหรับการ implement linked list นั้นเราสามารถเขียนออกมาได้ดังนี้เลย

(หลัก ๆ แล้ว linked list จะมี 3 operation คือ traverse หรือการท่องไปใน node ต่าง ๆ เพื่ออ่านค่าทั้งหมด หรือใช้ในการค้นหา, insertion หรือการเพิ่ม node, และ deletion หรือการลบ node)

1
// Function เอาไว้สำหรับสร้าง Node
2
function createNode(value) {
3
    return {value, next: null};
4
}
5


6
class LinkedList {
7
    constructor() {
8
        // เก็บ Node ตัวแรกสุด
9
        this.head = null;
10
        this.length = 0;
11
    }
12


13
    add(node) {
15 collapsed lines
14
        // กรณีที่ยังไม่มี Node อยู่เลย
15
        if (this.length === 0) {
16
            this.head = node;
17
            this.length += 1;
18
            return;
19
        }
20


21
        // ไปที่ Node ตัวท้ายสุดโดยไล่จาก Node ตัวแรก
22
        // จากนั้นแก้ next ตัวสุดท้ายไปที่ node ใหม่
23
        let currentNode = this.head;
24
        while (currentNode.next !== null) {
25
            currentNode = currentNode.next;
26
        }
27
        currentNode.next = node;
28
        this.length += 1;
29
    }
30


31
    remove(i) {
22 collapsed lines
32
        if (i < 0 || i >= this.length) {
33
            return;
34
        }
35


36
        // หา Node ที่ตรงตาม index
37
        let currIndex = 0;
38
        let currNode = this.head;
39
        let prevNode = null;
40
        while (currNode.next !== null && currIndex !== i) {
41
            prevNode = currNode;
42
            currNode = currNode.next;
43
            currIndex += 1;
44
        }
45


46
        // ถ้า prevNode = null หมายถึงลบตัวแรกสุด
47
        if (prevNode === null) {
48
            this.head = currNode.next;
49
        } else {
50
        // เอา Node ก่อนหน้าชี้ next ข้าม Node ที่จะลบ ไป Node ถัดไป
51
            prevNode.next = currNode.next;
52
        }
53
        this.length -= 1;
54
    }
55


56
    // Return ค่าทั้งหมดออกมาเป็น Array
57
    toArray() {
9 collapsed lines
58
        if (this.head === null) return [];
59


60
        const list = [];
61
        let currentNode = this.head;
62
        while (currentNode !== null) {
63
            list.push(currentNode.value);
64
            currentNode = currentNode.next;
65
        }
66
        return list;
67
    }
68
}
69


70
// ตัวอย่างการใช้งาน
71
const linkedList = new LinkedList();
6 collapsed lines
72
linkedList.add(createNode(10));
73
linkedList.add(createNode(15));
74
linkedList.add(createNode(20));
75
console.log(linkedList.toArray()); // [10, 15, 20]
76
linkedList.remove(1);
77
console.log(linkedList.toArray()); // [10, 20]

Time Complexity: add \(O(n)\), remove \(O(n)\), toArray \(O(n)\)

ลอง implement method insert(node, i) เพิ่ม โดย method นี้จะนำ node ไป insert ในตำแหน่งที่ i (Hint: ดูตัวอย่างจาก method delete)

Queue

ถ้าพูดถึงคำว่า ‘คิว’ เชื่อว่าหลายคนคงจะนึงถึงอะไรหลาย ๆ อย่างไกล้ตัวเช่น การต่อคิวเพื่อซื้อสินค้าอะไรบางอย่าง หรือการต่อคิวเพื่อกดบัตรคอนเสิร์ต ซึ่งถ้าหากเราลองนึกดี ๆ เราก็จะพบว่าสิ่งที่เรียกว่าคิวนั้น มี operation อยู่สองอย่างก็คือ ‘ต่อคิว’ และ ‘ออกจากคิว’ (โดยคนที่อยู่หน้าสุดจะเป็นคนออกจากคิวก่อน)

สำหรับ data structure ที่ชื่อว่า ‘Queue’ ก็เช่นกันครับ โดยสำหรับการต่อคิวหรือการ insert นั้นเราจะเรียกมันว่า ‘Enqueue’ และการออกจากคิวหรือการ delete นั้นเราจะเรียกมันว่า ‘Dequeue’

Queue

โดยสำหรับการ implement ‘Queue’ นั้นก็สามารถทำได้ตามนี้เลย

1
class Queue {
2
    constructor() {
3
        this.queue = [];
4
        // เก็บตำแหน่งหัวและท้ายของ queue
5
        this.head = -1;
6
        this.tail = -1;
7
    }
8


9
    enqueue(value) {
6 collapsed lines
10
        if (this.head === -1) {
11
            this.head = 0;
12
        }
13
        // ทำการเพิ่ม index ให้ tail จากนั้นเอาค่าใหม่ใส่ในตำแหน่งนั้น
14
        this.tail += 1;
15
        this.queue[this.tail] = value;
16
    }
17


18
    dequeue() {
7 collapsed lines
19
        if (this.head === -1 || this.head > this.tail) {
20
            return null;
21
        }
22
        // return ค่า head ออกมา จากนั้นเพิ่ม index ไป 1
23
        const head = this.queue[this.head];
24
        this.head += 1;
25
        return head;
26
    }
27
}
28


29
// ตัวอย่างการใช้งาน
30
const q = new Queue();
7 collapsed lines
31
q.enqueue(10);
32
q.enqueue(15);
33
q.enqueue(20);
34
console.log(q.dequeue()) // 10
35
console.log(q.dequeue()) // 15
36
console.log(q.dequeue()) // 20
37
console.log(q.dequeue()) // null

Time Complexity: enqueue \(O(1)\), dequeue \(O(1)\)

ในบางกรณี ข้อมูลของคิวก็อาจจะมีลำดับความสำคัญของตัวมันเอง ยกตัวอย่างเช่นการต่อคิวในโรงพยาบาล ถ้าหาก case ที่มีอาการร้ายแรงมาก ๆ อาจจะต้องได้รับการรักษาก่อนเคสที่อาการไม่ได้ร้ายแรงมากนักถึงแม้ว่าจะมาทีหลัง ดังนั้นแล้วเราอาจจะออกแบบ queue ของเราให้ dequeue ตัวที่มีความสำคัญสูงสุดออกมาก่อน ซึ่งเราจะเรียกคิวแบบนี้ว่า ‘Priority Queue’

Stack

เวลาเราพูดถึง Stack นั้นเราอาจจะนึกถึง ‘Stack of books’ หรือกองหนังสือ ที่เวลาเราอยากจะหยิบหนังสือเล่มไหนสักเล่มออกมา เราอาจจะหยิบเล่มที่อยู่ด้านบนสุดออกมาเรื่อย ๆ จนกระทั้งเจอเล่มที่เราต้องการจะอ่าน (จากนั้นค่อยวางเล่มอื่นกลับเข้าไปเหมือนเดิม)

Stack

สำหรับ operation ของ stack นั้นมีอยู่สองอย่างเหมือนกับ queue เลย ก็คือ insert กับ delete แต่เรามันจะเรียกมันว่า ‘Push’ คือการใส่ค่าใหม่เข้าไป และ ‘Pop’ หรือการเอาค่าบนสุดออกมา

อีกตัวอย่างนึงของการนำ stack มาใช้งานก็คือ “Web browsing history” ใน browser; สมมุติว่าตอนนี้เราเปิดเว็บ A อยู่จากนั้นไปเข้าเว็บ B เราก็จะเก็บ A ไว้ใน stack หลังจากนั้นพอเราไปกดเข้าเว็บ C เราก็จะ push B ไว้ใน stack (ณ ตอนนี้ stack จะมีค่า A, B) ถ้าเราจะกดปุ่มย้อนกลับ เราก็แค่ pop stack ออกมา

1
class Stack {
2
    constructor() {
3
        this.list = [];
4
        // เก็บตำแหน่งบนของ Stack
5
        this.top = -1;
6
    }
7


8
    push(value) {
2 collapsed lines
9
        this.top += 1;
10
        this.list[this.top] = value;
11
    }
12


13
    pop() {
7 collapsed lines
14
        if (this.top === -1) {
15
            return null;
16
        }
17


18
        const top = this.list[this.top];
19
        this.top -= 1;
20
        return top;
21
    }
22
}
23


24
// ตัวอย่างการใช้งาน
25
const s = new Stack();
7 collapsed lines
26
s.push(10);
27
s.push(15);
28
s.push(20);
29
console.log(s.pop()); // 20
30
console.log(s.pop()); // 15
31
console.log(s.pop()); // 10
32
console.log(s.pop()); // null

Time Complexity: push \(O(1)\), pop \(O(1)\)

(ส่วนสำหรับการ look up ข้อมูลนั้น สำหรับ queue จะ look up ได้เฉพาะแค่ตัวที่อยู่หน้าสุด และ stack จะ look up ได้เฉพาะตัวที่อยู่บนสุดเท่านั้น)

เรียกการจัดการข้อมูลของ Stack ว่า Last In First Out (LIFO) หรือก็คืออะไรที่เข้าไปทีหลังจะต้องออกมาก่อน ส่วนเราจะเรียกการจัดการข้อมูลของ Queue ว่า First In First Out (FIFO) หรืออะไรที่เข้าไปก่อนจะต้องออกมาก่อน

ทำไมถึงสำคัญ?

อย่างที่ได้เกริ่นไว้ใน section ที่แล้วว่า เวลาที่เรานึกถึง data structure หรือรูปแบบการจัดเก็บข้อมูลใดก็ตาม สิ่งหนึ่งที่แยกออกจากกันไม่ได้ก็คือ operation ต่าง ๆ หรือวิธีการจัดการข้อมูลที่เกี่ยวข้องกับ data structure นั้น

คำถามก็คือว่า “การที่เรารู้จัก data structure และ operation ต่าง ๆ นี้มันสำคัญอย่างไร? หรือ มันช่วยให้เราแก้ปัญหาได้ดีขึ้นได้อย่างไร?”

“ปัญหา” คืออะไร? มีโครงสร้างเป็นยังไง? และทำไมการเข้าใจคำ ๆ นี้ถึงสำคัญ
ปัญหาเป็นอะไรที่อยู่รอบตัวในชีวิตประจำวันของเราทุกคน แต่สิ่งที่เรามักเรียกมันจนเคยชินว่า “ปัญหา” จริง ๆ แล้วมันคืออะไร​?
February 26, 2024 | 10 mins read

(สำหรับนิยามของ “ปัญหาคืออะไร?” และ “อะไรคือวิธีแก้ปัญหาที่ดี?” นั้นสามารถอ่านเพื่อทำความเข้าใจกันก่อนได้ที่บทความข้างต้น)

ก่อนที่เราจะไปตอบคำถามข้างต้นนี้เราอาจจะต้องกลับมาย้อนดูกันก่อนว่า “เวลาเราแก้ปัญหาหนึ่ง ๆ กัน เราแก้มันยังไง หรือมีวิธีคิดยังไง?”

ถ้าเราลองถามทุกคนเล่น ๆ ว่า

“กำหนดให้ array ของตัวเลขมาค่าหนึ่ง ให้เขียน function เพื่อ return ค่าที่ duplicate กันทั้งหมดใน array นั้นออกมา”

ทุกคนจะเล่าวิธีคิดแก้ปัญหาของข้อนี้ออกมายังไง?

ถ้าเป็นเราคงจะบอกว่า “loop element แต่ละตัว จากนั้นเช็คว่าค่านั้นเคยโผล่มาแล้วใน map ไหม ถ้าเคยก็เก็บเป็นคำตอบ ถ้าไม่เคย ก็อัพเดตว่าค่านั้นเคยโผล่มาแล้วใน map”

คงจะไม่มีใครบอกว่า “สร้าง object มาตัวหนึ่ง จากนั้น loop ในแต่ละ index ของ array; กำหนดให้ตัวเลขใน index นั้นเป็น key และเช็คว่า key นี้ใน object เป็น true หรือไม่ ถ้าเป็นก็เก็บค่า key ลงคำตอบ ถ้าไม่ก็เซ็ต key ใน object ให้เป็น true …”

ความแตกต่างระหว่าง 2 แบบนี้ก็คือ แบบแรกคือเราคิดแบบ high level; เราไม่สนว่าสิ่งที่เรียกว่า map มัน implement ออกมาเป็นโค้ดได้อย่างไร (เราเรียก concept นี้ว่า ‘Abstraction’) เราสนแค่ว่าเราเอาสิ่งที่เรียกว่า map ซึ่งมี operation ก็คือการเช็ค (look up) กับการอัพเดตค่า (set/update) เอามาประกอบเป็นส่วนหนึ่งใน high level thinking ที่ใช้แก้ปัญหาของเราได้ยังไง (เราเรียก concept นี้ว่า ‘Composition’)

ในขณะที่แบบที่สองมันคือ psudo-code หรือแทบจะเป็น implementation แล้ว; เป็นสิ่งที่เราเขียนให้ computer อ่านเข้าใจ

“เวลาเราแก้ปัญหาใด ๆ ก็ตามเราคิดแบบที่ 1 ไม่ใช่แบบที่ 2” นั่นเป็นเพราะว่าเรา (ซึ่งเป็นมนุษย์คนหนึ่ง) ไม่สามารถที่จะ process ข้อมูลจำนวนมาก ๆ ได้เหมือน computer; นี่เป็นเหตุผลเดียวกันว่าทำไมเราถึงต้องแบ่ง function ต้องแยก module ย่อยของโค้ดต่าง ๆ ให้เป็นระเบียบ ก็เพื่อที่ข้อมูลจะเล็กพอให้เราสามารถ process มันในหัวเราได้นั่นเอง

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds

สำหรับเราแล้ว data structure ก็เป็นเหมือนกับเครื่องมือนึงนั่นหละ การที่เรารู้ data structure ที่หลากหลาย รวมถึง operation ต่าง ๆ ของแต่ละตัว มันช่วยลดสิ่งที่อยู่ในหัว และทำให้เราคิดแบบ high level thinking ได้ดีมากขึ้น

และการที่เรารู้ว่า data structure และ operation เหล่านั้นมัน implement อย่างไร ใช้ computational complexity เท่าไหร่ มันทำให้เราสามารถที่จะ make trade off ที่ตอบโจทย์กับ context ของปัญหาที่เราวางไว้ ได้นั่นเอง

Exercises

  1. ถ้าหากว่าคุณได้รับมอบหมายให้พัฒนาห้องสมุดต่อจาก v3 คุณจะพัฒนาต่อในแง่ไหน ด้วยวิธีการไหน? ลองคิดไอเดียออกมาให้ได้มากที่สุด
  2. สำหรับห้องสมุด v3 ตอนทำ batch processing ตอนยืมหนังสือนั้น; ถ้าหากว่าเรามี array ของตัวเลข ที่อาจะมีค่าบางค่าใน array เป็น null เราจะออกแบบ algorithm อย่างไรเพื่อ shift element ทั้งหมดให้มาอยู่ติดกันด้านหน้าของ array? และใช้ Time complexity เท่าไหร่?
  3. ลองยกตัวอย่าง data structure อื่น ๆ ที่ไม่มีในบทนี้มา 3 ตัว แต่ละตัวมี operation อะไรบ้าง และแต่ละ operation ใช้ time complexity เท่าไหร่?
  4. จากโค้ดตัวอย่าง linked list; ลองเขียน doubly และ circular linked list จากโค้ดดังกล่าว
  5. ลอง implement ‘Priority Queue’ โดยไม่ต้องสนว่า time complexity จะต้องออกมาดีที่สุด

Challenge Problem

โจทย์กำหนดให้รับ input มาหนึ่งตัวเป็น string s ที่ character แต่ละตัว เป็นไปได้แค่หนึ่งใน 6 ตัวนี้: ( ) [ ] { }; ให้เขียนโค้ดเพื่อเช็คว่า string ดังกล่าวเป็น ‘valid parentheses’ หรือไม่ (return ค่าออกมาเป็น boolean: true, false)

string จะเป็น valid parentheses ก็ต่อเมื่อ:

  1. ในแต่ละวงเล็บเปิด จะต้องมีวงเล็บปิดที่มีชนิดเดียวกันตามมาปิดด้วยเสมอ
  2. การเปิดและปิดของวงเล็บทั้งหมดมีลำดับที่ถูกต้อง

Example 1:

Input: "()"

Output: true

Example 2:

Input: "()[]{}"

Output: true

Example 3:

Input: "(]"

Output: false

Example 4:

Input: "({)}"

Output: false

Example 5:

Input: "([{}])"

Output: true

Solution #1

ก่อนอื่นเลยเรามาเริ่มจากการทำความเข้าใจ test cases ของเรากันก่อน; ถ้าหากว่าเราสังเกตรูปแบบข้อมูลของ input ข้อนี้เราจะพบว่ามันมีโครงสร้างที่ซ้อนกันอยู่ (nested structure) ยกตัวอย่างเช่น Example ที่ 5: ([{}]) ที่ภายใน (..) จะสามารถมีวงเล็บอื่น ๆ อยู่ [{}]

เราสามารถสรุปออกมาเป็น observation คร่าว ๆ ได้ดังนี้ครับ (ในเคสที่เป็น valid parentheses)

  1. ภายในวงเล็บใดวงเล็บหนึ่ง สามารถมีวงเล็บอื่น ๆ อยู่ภายในนั้นอีกกี่ตัวได้ เช่น ([{}]) หรือ ([{}][{}()]) หรือพูดอีกนัยหนึ่งคือ ภายในวงเล็บหนึ่งสามารถมี valid parentheses อยู่ในนั้นได้ เช่น (valid parentheses) หรือ [valid parentheses]
  2. (), {}, [] สามตัวนี้เป็น valid parentheses ที่ภายในจะไม่มีวงเล็บอื่น ๆ อยู่แล้ว

ก่อนที่เราจะมาเริ่มต้นคิดวิธีแก้ปัญหาข้อนี้กันเรามา simplify ปัญหาเพิ่มเติมกันหน่อย: “เริ่มจาก ‘วงเล็บประเภทเดียว’ ก่อน จากนั้นพอหาวิธีแก้ได้แล้วค่อยไป apply กับวงเล็บประเภทอื่น ๆ”

โดยเราอาจจะเริ่มจาก test cases ง่าย ๆ กันก่อน

  1. "()": เป็น valid parentheses ตาม observation ที่สอง
  2. "(())": จะเห็นว่าวงเล็บตรงกลางเป็น valid parentheses เราอาจจะเขียนได้ว่า "(valid)" ซึ่งถ้าเราตัด valid ออกไป (ในเมื่อมัน valid เราก็ไม่จำเป็นต้องสนมันแล้ว เราสนวงเล็บที่ครอบมันมากกว่าว่ามัน valid ไหม) สิ่งที่เหลืออยู่ก็คือ "()" ซึ่งเป็น valid parentheses
  3. เราสามารถใช้วิธีการตัด () แบบเดียวกับ input อื่น ๆ ได้เช่น "(())()" หรือ "((())())"

จาก test cases ตรงนี้เราสามารถสรุปออกมาได้ดังนี้ครับ

  1. ถ้าเราตัด () ออกไปเรื่อย ๆ จนกระทั้ง string ไม่เหลืออะไรให้ตัดแล้ว (empty string) เราสามารถสรุปได้ว่า string นี้เป็น valid parentheses
  2. ถ้าเราค่อย ๆ ไล่ไปในแต่ละตัวอักษรของ string; ทุกครั้งที่มีวงเล็บปิดเกิดขึ้น ‘เราจะสามารถตัด () ออกได้เสมอ’ (ในกรณีที่ string เป็น valid parentheses)

จากข้อสังเกตตรงนี้เราสามารถเขียน algorithm ของเราออกมาได้ว่า:

  1. loop ไปในแต่ละตัวอักษรของ string s
  2. ถ้าหากว่า s[i] เป็นวงเล็บเปิด "(" ก็ไม่ต้องทำอะไร
  3. ถ้าหากว่า s[i] เป็นวงเล็บปิด ")" ก็ให้เช็คว่าตัวก่อนหน้าเป็นวงเล็บเปิด "(" หรือไม่
    • ถ้าหากว่าใช่ก็ให้หักลบกันออกไป
  4. เมื่อจบการทำงานเช็คว่ามีอักษรไหนที่หลงเหลือไม่ถูกตัดออกหรือไม่ ถ้าไม่มีก็ return true แต่ถ้าหากว่ามีก็แสดงว่ามีวงเล็บที่เปิดแล้วไม่ถูกปิด หรือมีการปิดเกิน ดังนั้น return false

สำหรับการ implement นั้นเราสามารถใช้ ‘HashMap’ ในการเช็คคู่ของวงเล็บเปิดปิดได้ (อย่าลืมว่าตอนนี้เรา simplify อยู่ จริง ๆ แล้วมีวงเล็บ 3 ชนิด) และเราสามารถใช้ ‘Stack’ ในการหักลบตัวที่เป็นคู่กันได้ (การ manipulate string ตรง ๆ เป็นอะไรที่ซับซ้อนและใช้ cost สูง)

โดยสรุปแล้วเราสามารถเขียน psudo-code ออกมาได้ดังนี้:

  1. loop ไปในแต่ละตัวอักษรของ string s
  2. ถ้าหากว่า s[i] เป็นวงเล็บเปิด; push s[i] ลงใน stack
  3. ถ้าหากว่า s[i] เป็นวงเล็บปิด ก็ให้เช็คว่า top ของ stack เป็นวงเล็บเปิดชนิดเดียวกันหรือไม่
    • ถ้าใช่: ทำการ pop ตัวบนสุดของ stack ออก
    • ถ้าไม่: ทำการ push s[i] ลงใน stack
  4. เช็คว่า stack ว่างไหม

โดยเราสามารถเขียนโค้ดออกมาได้ดังนี้เลย (ในที่นี้ขอใช้โค้ด stack ที่เขียนกันไว้ในบทนี้)

1
class Stack {
23 collapsed lines
2
  constructor() {
3
    this.list = [];
4
    this.top = -1;
5
  }
6


7
  push(value) {
8
    this.top += 1;
9
    this.list[this.top] = value;
10
  }
11


12
  pop() {
13
    if (this.top === -1) {
14
      return null;
15
    }
16


17
    const top = this.list[this.top];
18
    this.top -= 1;
19
    return top;
20
  }
21


22
  getTop() {
23
    return this.top !== -1 ? this.list[this.top] : null;
24
  }
25
}
26


27
function isValid(s) {
28
  const stack = new Stack();
29
  const pairMap = {
30
    "(": ")",
31
    "[": "]",
32
    "{": "}",
33
  };
34


35
  for (let i = 0; i < s.length; ++i) {
36
    // เช็คว่าเป็นวงเล็บเปิดไหม
37
    if (pairMap[s[i]]) {
38
      stack.push(s[i]);
39
      continue;
40
    }
41


42
    // เช็คว่ามีชนิดเดียวกันหรือไม่
43
    if (pairMap[stack.getTop()] === s[i]) {
44
      stack.pop();
45
    } else {
46
      stack.push(s[i]);
47
    }
48
  }
49


50
  return stack.getTop() === null;
51
};

Time Complexity: \(O(n)\) หรือ \(O(s.length)\)

Published: May 23, 2024
Updated: May 23, 2024
Reading time: 29 mins

Table of Contents

Contact: [email protected]

© 2024 LearnAlgorithm.com, All rights reserved.

Made with by Chun Rapeepat