선형시간으로 최대값과 최소값 찾기

문제

배열을 정렬을 하지 않고도 선형시간으로 최대값과 최소값을 찾을 수 있다.

접근법

배열의 크기가 짝수인지 또는 홀수인지에 따라 나뉜다. 홀수인 경우에는 추가작업이 필요하다. 공통 접근법은 다음과 같다.

• 배열의 인덱스 0번과 1번 자리를 각각 최소자리와 최대자리로 지정한다.
• 배열을 2만큼씩 간격으로 i번째와 i+1번째의 값의 크기를 비교한다. i번째가 더 크다면 두 값의 위치를 교체한다.
• 0번째 값은 i번째와 비교하여 0번째가 값이 더 큰 경우에 위치를 교체한다.
• 1번째 값은 i+1번째와 비교하여 1번째가 값이 더 큰 경우에 위치를 교체한다.
• 배열의 크기가 짝수인 경우에 배열 전부에 위의 과정을 반복하고 홀수인 경우에는 마지막 원소를 제외하고 실행한다.
• 짝수 크기의 배열은 0번째가 최소값, 1번째가 최대값이 된다.
• 홀수 크기의 배열은 마지막 원소를 0번째와 1번째 원소와 값을 비교하여 최소값과 최대값을 조정한다.

구현

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {8, 2, 3, 5, 9, 1, 9, 4, 3, 7, 6, 7, 10};

    // REVIEW
    // 배열이 짝수인 경우 필요한 부분
    int count = 0;
    for (int i = 0; i < arr.size() - 1; i += 2) {
        count += 1;
        if (arr[i] > arr[i + 1]) {
            swap(arr[i], arr[i + 1]);
        }

        if (arr[0] > arr[i]) {
            swap(arr[0], arr[i]);
        }
        if (arr[1] < arr[i + 1]) {
            swap(arr[1], arr[i + 1]);
        }
    }

    // 배열이 홀수인 경우 처리
    if (arr[0] > arr[arr.size() - 1]) {
        swap(arr[0], arr[arr.size() - 1]);
    }

    if (arr[1] < arr[arr.size() - 1]) {
        swap(arr[1], arr[arr.size() - 1]);
    }

    cout << count << endl;
    cout << "Min value = " << arr[0] << ", Max value = " << arr[1] << endl; // Min value = 1, Max value = 9
}

코드를 실행하면 count는 6을 출력한다. 비교코드까지 고려하면 전체 코드의 명령횟수는 20번이다. 이는 배열의 크기(20)의 선형배수다. 정렬을 한 후에 최소값과 최대값을 찾으려면 O(N^2)이거나 아무리 효율이 좋아도 O(NlogN)이다. 정렬을 할 필요가 없다면 선형시간으로 최대값과 최소값을 찾는게 더 효율적이다.