C++ 배열에서 첫 번째, 두 번째, 세 번째 최솟값 찾기

문제 개요

n개의 요소로 구성된 배열이 있다고 가정해 보겠습니다. 이 배열에서 첫 번째, 두 번째, 세 번째 최솟값을 찾아야 합니다.

여기서 각 용어의 의미는 다음과 같습니다.

첫 번째 최솟값(first min): 배열 전체에서 가장 작은 값
두 번째 최솟값(second min): 첫 번째 최솟값보다 큰 값들 중 가장 작은 값
세 번째 최솟값(third min): 두 번째 최솟값보다 큰 값들 중 가장 작은 값

접근 방법

이 문제는 배열의 각 요소를 한 번씩 순회하면서, 현재 요소가 첫 번째·두 번째·세 번째 최솟값 조건에 해당하는지 검사하는 방식으로 해결할 수 있습니다.

알고리즘 단계

first, sec, third 세 개의 변수를 각각 INT_MAX(정수형 최댓값)로 초기화합니다.
배열을 처음부터 끝까지 순회하며 다음 조건을 검사합니다.
- 현재 요소가 first보다 작으면 → third = sec, sec = first, first = arr[i] 순으로 값을 한 칸씩 밀어냅니다.
- 그렇지 않고 현재 요소가 sec보다 작으면 → third = sec, sec = arr[i]로 갱신합니다.
- 그렇지 않고 현재 요소가 third보다 작으면 → third = arr[i]로 갱신합니다.
순회가 끝나면 세 변수에는 각각 첫 번째, 두 번째, 세 번째 최솟값이 저장됩니다.

C++ 예제 코드

#include<iostream>
using namespace std;

int getThreeMins(int arr[], int n) {
    int first = INT_MAX, sec = INT_MAX, third = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (arr[i] < first) {
            third = sec;
            sec = first;
            first = arr[i];
        } else if (arr[i] < sec) {
            third = sec;
            sec = arr[i];
        } else if (arr[i] < third)
            third = arr[i];
    }
    cout << "First min = " << first << endl;
    cout << "Second min = " << sec << endl;
    cout << "Third min = " << third << endl;
}

int main() {
    int array[] = {4, 9, 18, 32, 12};
    int n = sizeof(array) / sizeof(array[0]);
    getThreeMins(array, n);
}

실행 결과

First min = 4
Second min = 9
Third min = 12

위 예제에서 배열 {4, 9, 18, 32, 12}의 경우 가장 작은 값은 4, 그다음으로 작은 값은 9, 세 번째로 작은 값은 12임을 확인할 수 있습니다.

복잡도 분석

시간 복잡도: O(n) — 배열을 단 한 번만 순회하므로 매우 효율적입니다.
공간 복잡도: O(1) — 추가 메모리 없이 세 개의 변수만 사용합니다.

배열을 정렬한 뒤 앞의 세 요소를 가져오는 방법(O(n log n))보다, 위와 같은 단일 순회 방식이 더 빠르고 효율적이라는 점이 이 알고리즘의 핵심 장점입니다.