Array

 

개요

동일 자료형 원소들의 sequence.

 

TYPENAME name[SIZE] 의 꼴로 쓴다.

 

 

Array의 성질

index를 이용해 각 원소를 임의 참조할 수 있다. [0 : N)

 

크기를 미리 정해야 한다.

 

 

Insertion

index i에 원소 e를 삽입할 때, index가 i 이상인 모든 원소를 shift 한다. $O(n)$

 

 

Deletion

index i의 원소를 삭제할 때, index가 i 이상인 모든 원소를 shift 한다. $O(n)$

 

Array의 원소들은 연속하여야 하기 때문이다.

 

 

Implementation

아래는 이론에서 배운 내용을 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

/*

# Insert(i, e)		O(n)
# Remove(i)		O(n)
# at(i)			O(1)
# set(i)		O(1)

*/

struct Array {
	int* arr;
	int maxSize, size;

	Array(int ms) {
		maxSize = ms;
		size = 0;
		arr = new int[maxSize];
		for (int i = 0; i < maxSize; ++i) arr[i] = 0;
	}
	~Array() {
		delete arr;
	}

	int at(int id) {
		return arr[id];
	}
	void set(int id, int data) {
		if (at(id) == 0) {
			cout << 0 << "\n";
			return;
		}
		arr[id] = data;
	}
	void add(int id, int data) {
		if (id >= size) arr[size] = data;
		else {
			for (int i = size; i > id; --i) arr[i] = arr[i - 1];
			arr[id] = data;
		}
		size++;
	}
	void remove(int id) {
		if (id >= size) {
			cout << 0 << "\n";
			return;
		}
		for (int i = id; i < size; ++i) arr[i] = arr[i + 1];
		size--;
	}
};

int main() {
	Array A(10000);
	int TEST; cin >> TEST; while (TEST--) {
		string oper; int p, q; cin >> oper;
		if (oper == "at") {
			cin >> p; cout << A.at(p) << "\n";
		}
		else if (oper == "add") {
			cin >> p >> q; A.add(p, q);
		}
		else if (oper == "set") {
			cin >> p >> q; A.set(p, q);
		}
		else if (oper == "del") {
			cin >> p; A.remove(p);
		}
	}
}