JavaScript를 사용하여 DSA에 배열 삽입: 기초부터 고급까지

배열은 컴퓨터 과학의 기본 데이터 구조이며 배열을 효율적으로 조작하는 방법을 이해하는 것은 모든 개발자에게 중요합니다. 이 블로그 게시물에서는 JavaScript를 사용한 배열 삽입 기술에 대해 자세히 알아보고 기본 수준부터 고급 수준까지 개념을 다룹니다. 다양한 시나리오를 탐색하고, 20가지 예를 제공하고, 시간 복잡성에 대해 논의하고, 심지어 LeetCode 스타일 문제도 다룰 것입니다.

목차

1. 배열 소개
2. 기본 배열 삽입
3. 특정 위치에 삽입
4. 여러 요소 삽입
5. 효율적인 삽입 기법
6. 고급 삽입 시나리오
7. LeetCode 스타일 문제
8. 연습 문제

1. 배열 소개

배열은 인접한 메모리 위치에 저장된 요소의 모음입니다. JavaScript에서 배열은 동적입니다. 즉, 크기가 늘어나거나 줄어들 수 있습니다. 삽입 기술에 대해 알아보기 전에 JavaScript 배열의 기본 사항을 빠르게 요약해 보겠습니다.

// Creating an array
let fruits = ['apple', 'banana', 'orange'];

// Accessing elements
console.log(fruits[0]); // Output: 'apple'

// Getting array length
console.log(fruits.length); // Output: 3

2. 기본 배열 삽입

예 1: 끝에 삽입(푸시)

배열에 요소를 삽입하는 가장 간단한 방법은 push() 메서드를 사용하여 끝에 추가하는 것입니다.

let numbers = [1, 2, 3];
numbers.push(4);
console.log(numbers); // Output: [1, 2, 3, 4]

시간 복잡도: O(1) - 상수 시간

예 2: 처음에 삽입(unshift)

배열의 시작 부분에 요소를 삽입하려면 unshift() 메서드를 사용하세요.

let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']

시간 복잡도: O(n) - 선형 시간, 여기서 n은 배열의 요소 수

예 3: 스프레드 연산자를 사용하여 삽입

확산 연산자를 사용하여 추가 요소가 포함된 새 배열을 만들 수 있습니다.

let animals = ['cat', 'dog'];
let newAnimals = ['bird', ...animals, 'fish'];
console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']

시간 복잡도: O(n) - 선형 시간, 여기서 n은 새 배열의 총 요소 수입니다

3. 특정 위치에 삽입하기

예제 4: splice()를 사용하여 특정 인덱스에 삽입

splice() 메서드를 사용하면 배열의 특정 위치에 요소를 삽입할 수 있습니다.

let fruits = ['apple', 'banana', 'orange'];
fruits.splice(1, 0, 'mango');
console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']

시간 복잡도: O(n) - 선형 시간, 여기서 n은 삽입 지점 뒤의 요소 수

예제 5: splice()를 사용하여 여러 요소 삽입

splice()를 사용하면 여러 요소를 한 번에 삽입할 수 있습니다.

let numbers = [1, 2, 5, 6];
numbers.splice(2, 0, 3, 4);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]

시간 복잡도: O(n) - 선형 시간, 여기서 n은 삽입 지점 뒤의 요소 수

예 6: 요소 덮어쓰기

배열 인덱싱을 사용하여 특정 위치의 요소를 덮어쓸 수도 있습니다.

let letters = ['A', 'B', 'D', 'E'];
letters[2] = 'C';
console.log(letters); // Output: ['A', 'B', 'C', 'E']

시간 복잡도: O(1) - 상수 시간

4. 여러 요소 삽입

예제 7: 배열 연결

concat() 메소드를 사용하여 여러 배열을 결합할 수 있습니다.

let arr1 = [1, 2];
let arr2 = [3, 4];
let arr3 = [5, 6];
let combined = arr1.concat(arr2, arr3);
console.log(combined); // Output: [1, 2, 3, 4, 5, 6]

시간 복잡도: O(n) - 선형 시간, 여기서 n은 모든 배열의 총 요소 수입니다

예제 8: Spread 연산자와 함께 push() 사용

push()를 스프레드 연산자와 함께 사용하여 끝에 여러 요소를 삽입할 수 있습니다.

let numbers = [1, 2, 3];
let newNumbers = [4, 5, 6];
numbers.push(...newNumbers);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]

시간 복잡도: O(m) - 선형 시간, 여기서 m은 삽입되는 요소 수

예 9: 다른 어레이에 어레이 삽입

전체 배열을 특정 위치의 다른 배열에 삽입하는 방법은 다음과 같습니다.

function insertArray(mainArray, subArray, position) {
    return [...mainArray.slice(0, position), ...subArray, ...mainArray.slice(position)];
}

let main = [1, 2, 5, 6];
let sub = [3, 4];
console.log(insertArray(main, sub, 2)); // Output: [1, 2, 3, 4, 5, 6]

시간 복잡도: O(n) - 선형 시간, 여기서 n은 결과 배열의 총 요소 수입니다

5. 효율적인 삽입 기술

예제 10: 배열 크기 사전 할당

배열의 최종 크기를 알고 있는 경우 사전 할당을 통해 성능을 향상할 수 있습니다.

function createSequence(n) {
    let arr = new Array(n);
    for (let i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    return arr;
}

console.log(createSequence(5)); // Output: [1, 2, 3, 4, 5]

시간 복잡도: O(n) - 선형 시간이지만 배열을 동적으로 확장하는 것보다 효율적입니다

예제 11: 숫자 데이터에 대해 형식화된 배열 사용

숫자 데이터의 대규모 배열의 경우 형식화된 배열을 사용하는 것이 더 효율적일 수 있습니다.

let floatArray = new Float64Array(5);
for (let i = 0; i < 5; i++) {
    floatArray[i] = i * 1.1;
}
console.log(floatArray); // Output: Float64Array(5) [0, 1.1, 2.2, 3.3000000000000003, 4.4]

시간 복잡도: O(n) - 선형 시간이지만 숫자 데이터의 경우 메모리 효율성이 더 좋습니다

예 12: 일괄 삽입

여러 요소를 삽입할 때는 한 번에 하나씩 삽입하는 것보다 일괄적으로 삽입하는 것이 더 효율적일 수 있습니다.

function batchInsert(arr, elements, batchSize = 1000) {
    for (let i = 0; i < elements.length; i += batchSize) {
        arr.push(...elements.slice(i, i + batchSize));
    }
    return arr;
}

let numbers = [1, 2, 3];
let newNumbers = Array.from({ length: 10000 }, (_, i) => i + 4);
console.log(batchInsert(numbers, newNumbers).length); // Output: 10003

시간 복잡도: O(n) - 선형 시간이지만 대규모 삽입에 더 나은 성능을 제공합니다

6. 고급 삽입 시나리오

예제 13: 정렬된 배열에 삽입

정렬된 배열에 삽입할 때 이진 검색을 사용하여 올바른 위치를 찾을 수 있습니다.

function insertSorted(arr, element) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] < element) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    arr.splice(left, 0, element);
    return arr;
}

let sortedArray = [1, 3, 5, 7, 9];
console.log(insertSorted(sortedArray, 4)); // Output: [1, 3, 4, 5, 7, 9]

시간 복잡도: 위치 찾기 O(log n) + 삽입 O(n) = O(n)

실시예 14: 순환 버퍼 삽입

순환 버퍼는 둘러싸는 고정 크기 배열입니다. 순환 버퍼에 삽입하는 방법은 다음과 같습니다.

class CircularBuffer {
    constructor(size) {
        this.buffer = new Array(size);
        this.size = size;
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }

    insert(element) {
        this.buffer[this.tail] = element;
        this.tail = (this.tail + 1) % this.size;
        if (this.count < this.size) {
            this.count++;
        } else {
            this.head = (this.head + 1) % this.size;
        }
    }

    getBuffer() {
        return this.buffer.slice(this.head, this.head + this.count);
    }
}

let cb = new CircularBuffer(3);
cb.insert(1);
cb.insert(2);
cb.insert(3);
cb.insert(4);
console.log(cb.getBuffer()); // Output: [2, 3, 4]

Time Complexity: O(1) for insertion

Example 15: Sparse Array Insertion

Sparse arrays have "empty" slots. Here's how to work with them:

let sparseArray = new Array(5);
sparseArray[2] = 'Hello';
sparseArray[4] = 'World';
console.log(sparseArray); // Output: [empty × 2, 'Hello', empty, 'World']
console.log(sparseArray.length); // Output: 5

// Iterating over sparse array
sparseArray.forEach((item, index) => {
    if (item !== undefined) {
        console.log(`${index}: ${item}`);
    }
});
// Output:
// 2: Hello
// 4: World

Time Complexity: O(1) for insertion, O(n) for iteration

Example 16: Insertion with Deduplication

When inserting elements, you might want to avoid duplicates:

function insertUnique(arr, element) {
    if (!arr.includes(element)) {
        arr.push(element);
    }
    return arr;
}

let uniqueNumbers = [1, 2, 3, 4];
console.log(insertUnique(uniqueNumbers, 3)); // Output: [1, 2, 3, 4]
console.log(insertUnique(uniqueNumbers, 5)); // Output: [1, 2, 3, 4, 5]

Time Complexity: O(n) due to the includes check

Example 17: Insertion with Priority

Implementing a basic priority queue using an array:

class PriorityQueue {
    constructor() {
        this.queue = [];
    }

    insert(element, priority) {
        const item = { element, priority };
        let added = false;
        for (let i = 0; i < this.queue.length; i++) {
            if (item.priority < this.queue[i].priority) {
                this.queue.splice(i, 0, item);
                added = true;
                break;
            }
        }
        if (!added) {
            this.queue.push(item);
        }
    }

    getQueue() {
        return this.queue.map(item => item.element);
    }
}

let pq = new PriorityQueue();
pq.insert('Task 1', 2);
pq.insert('Task 2', 1);
pq.insert('Task 3', 3);
console.log(pq.getQueue()); // Output: ['Task 2', 'Task 1', 'Task 3']

Time Complexity: O(n) for insertion

Example 18: Dynamic 2D Array Insertion

Creating and inserting into a dynamic 2D array:

function create2DArray(rows, cols) {
    return Array.from({ length: rows }, () => new Array(cols).fill(0));
}

function insert2D(arr, row, col, value) {
    // Expand array if necessary
    while (arr.length <= row) {
        arr.push([]);
    }
    while (arr[row].length <= col) {
        arr[row].push(0);
    }
    arr[row][col] = value;
}

let matrix = create2DArray(2, 2);
insert2D(matrix, 1, 1, 5);
insert2D(matrix, 3, 3, 7);
console.log(matrix);
// Output: [
//   [0, 0],
//   [0, 5],
//   [0],
//   [0, 0, 0, 7]
// ]

Time Complexity: O(1) average case, O(n) worst case when expanding the array

Example 19: Insertion into a Trie (Prefix Tree)

While not strictly an array, a trie uses arrays (or objects) internally and is useful for string insertions:

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                current.children[char] = new TrieNode();
            }
            current = current.children[char];
        }
        current.isEndOfWord = true;
    }

    search(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                return false;
            }
            current = current.children[char];
        }
        return current.isEndOfWord;
    }
}

let trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.search("apple")); // Output: true
console.log(trie.search("app")); // Output: true
console.log(trie.search("appl")); // Output: false

Time Complexity: O(m) for insertion and search, where m is the length of the word

Example 20: Insertion with Custom Sorting

Inserting elements while maintaining a custom sort order:

function insertSorted(arr, element, compareFn) {
    let index = arr.findIndex(item => compareFn(element, item) <= 0);
    if (index === -1) {
        arr.push(element);
    } else {
        arr.splice(index, 0, element);
    }
    return arr;
}

// Example: Sort by string length, then alphabetically
let words = ['cat', 'elephant', 'dog'];
let compareFn = (a, b) => {
    if (a.length !== b.length) {
        return a.length - b.length;
    }
    return a.localeCompare(b);
};

console.log(insertSorted(words, 'bear', compareFn));
// Output: ['cat', 'dog', 'bear', 'elephant']

Time Complexity: O(n) for finding the insertion point + O(n) for insertion = O(n)

7. LeetCode-Style Problems

Now that we've covered various insertion techniques, let's look at some LeetCode-style problems that involve array insertions.

Problem 1: Insert Interval

Given a sorted array of non-overlapping intervals and a new interval, insert the new interval and merge if necessary.

function insert(intervals, newInterval) {
    let result = [];
    let i = 0;

    // Add all intervals that come before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }

    // Add the merged interval
    result.push(newInterval);

    // Add remaining intervals
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

console.log(insert([[1,3],[6,9]], [2,5]));
// Output: [[1,5],[6,9]]

Time Complexity: O(n), where n is the number of intervals

Problem 2: Merge Sorted Array

Given two sorted arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

function merge(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;

merge(nums1, m, nums2, n);
console.log(nums1);
// Output: [1,2,2,3,5,6]

Time Complexity: O(m + n), where m and n are the lengths of nums1 and nums2 respectively

8. Practice Problems

To further test your understanding of array insertions, here are 15 LeetCode problems that involve various aspects of array manipulation and insertion:

1. Insert Interval
2. Merge Sorted Array
3. Insert Delete GetRandom O(1)
4. Search Insert Position
5. Array Partition I
6. Maximum Subarray
7. Move Zeroes
8. Sort Colors
9. Merge Intervals
10. Next Permutation
11. Find First and Last Position of Element in Sorted Array
12. 3Sum
13. Container With Most Water
14. Rotate Array
15. Product of Array Except Self

These problems cover a wide range of difficulty levels and will help you practice various array insertion and manipulation techniques.

Conclusion

Array insertion is a fundamental operation in data structures and algorithms. As we've seen, there are many ways to insert elements into arrays, each with its own use cases and time complexities. From simple push operations to more complex scenarios like maintaining sorted order or implementing data structures like circular buffers and tries, understanding these techniques will greatly enhance your ability to work with arrays efficiently.

Remember that the choice of insertion method can significantly impact the performance of your algorithm, especially when dealing with large datasets. Always consider the specific requirements of your problem and the trade-offs between time and space complexity when choosing an insertion technique.

Practice with the provided examples and LeetCode problems to solidify your understanding and improve your problem-solving skills.

Happy coding!

위 내용은 JavaScript를 사용하여 DSA에 배열 삽입: 기초부터 고급까지의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!