정렬되지 않은 배열에서 요소를 삭제하는 방법
삭제 연산은 선형 탐색을 이용하여 삭제할 요소를 검색한 후 요소를 이동시킨 후 삭제 연산을 진행합니다.
public class UnsortedDelete {
static int findElement(int arr[], int n, int key) {
for(int i =0; i < n; i++) {
if(arr[i] == key) return i;
}
return -1;
}
static int deleteElement(int arr[], int n, int key) {
int pos = findElement(arr, n ,key);
if(pos == -1) {
System.out.println("element not found");
return n;
}
for(int i = pos; i < n -1; i++) {
arr[i] = arr[i+1];
}
return n - 1;
}
public static void main(String args[])
{
int i;
int arr[] = { 10, 50, 30, 40, 20 };
int n = arr.length;
int key = 30;
n = deleteElement(arr, n, key);
for (i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
삭제할 원소를 찾은 후 해당 인덱스부터 하나씩 왼쪽으로 이동시켜 삭제시킵니다.
정렬된 배열에서 요소를 삭제하는 방법
정렬된 배열에서 삭제 연산은 이진 탐색을 이용하여 삭제할 요소를 검색한 후 해당 요소를 이동시킨 후 삭제를 시킵니다.
public class SortedDelete {
public static void main(String[] args) {
int i;
int arr[] = { 10, 50, 30, 40, 20 };
int n = arr.length;
int key = 30;
n = deleteElement(arr, n, key);
for (i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
static int binarySearch(int arr[], int low, int high, int key) {
if(high < low) return -1;
int mid = (low + high) / 2;
if(key == arr[mid]) return mid;
else if(key > arr[mid]) return binarySearch(arr, mid + 1, high, key);
else return binarySearch(arr, low, mid - 1, key);
}
static int deleteElement(int arr[], int n, int key) {
int pos = binarySearch(arr, 0, n ,key);
if(pos == -1) {
System.out.println("element not found");
return n;
}
for(int i = pos; i < n -1; i++) {
arr[i] = arr[i+1];
}
return n - 1;
}
}
'알고리즘 > 자료구조' 카테고리의 다른 글
문자열 연산하기(삽입, 수정, 삭제, 비교) (0) | 2024.04.19 |
---|---|
문자열이란 무엇인가? (0) | 2024.04.09 |
배열 원소 검색으로 값 찾는 방법(선형 검색, 이진 검색, 피보나치 검색) (0) | 2024.04.09 |
배열 삽입의 모든 것 (0) | 2024.04.09 |
배열 요소에 접근하는데 O(1)의 시간이 걸리는 이유 (0) | 2024.04.04 |