순차탐색과 정렬의 효과

순차탐색

원하는 값이 존재하는 지 확인을 하기 위해 배열의 앞에서부터 뒤까지 탐색하는 과정이다. 값이 존재한다면 그 위치를, 없다면 -1을 반환한다.

int SequentialSearch(int *arr, int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

배열의 정렬 시 순차탐색의 효율성

배열이 정렬되어 있는 경우에 순차탐색을 더욱 빠르게 할 수 있다. 목표 값을 찾는 경우에 배열의 순회를 중단할 수 있기 때문이다.

활용: 값의 개수 세기

값의 개수를 셀 때 배열을 정렬한 후에 순차탐색을 하는 것이 효율적이다.

int SequentialSearch(int *arr, int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int SortedCountHelper(int *arr, int n, int x, int start) // start 사용
{
    int count = 0;
    for (int i = start; i < n; i++) {
        if (arr[i] != x) {
            break;
        }
        count += 1;
    }
    return count;
}

int SortedCount(int *arr, int n, int x) {
		InsertionSort(arr, n); // 배열 정렬
    int i = SequentialSearch(arr, n, x); // x의 첫번째 위치 반환

    if (i >= 0)
        return SortedCountHelper(arr, n, x, i + 1) + 1; // 다음 위치부터 갯수 세기
    else
        return 0;
}

 

활용: 문자열 압축문제

문자열이 주어졌을 때 문자 하나당 개수만큼 붙여서 변환하는 문제다. 문자열 전체를 순회하면서 문자 하나하나의 개수를 세야한다. 성능을 위해 문자열을 정렬한 후에 문자열을 순회하면서 문자가 변할 때마다 지정을 하고 개수를 세는게 좋다.

void compress_string(char *arr, int n) { // arr은 문자열, n은 문자열의 크기
    InsertionSort(arr, n); // 문자열 정렬

    cout << arr << endl;

    char c = arr[0]; // 첫번째 글자부터 시작
    int count = 1; // 1부터 셈

    cout << c;

    for (int i = 1; i < n; i++) {
        if (arr[i] == c) {
            count += 1;
        } else {
            cout << count;// 결과 출력
            c = arr[i]; // 문자 갱신
            count = 1; // 다시 1부터 시작
            cout << c; // 문자 출력
        }
    }

    cout << count << endl; // 마지막 count 출력
}