n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 이 배열에서 첫 번째, 두 번째, 세 번째 최솟값을 찾아야 합니다. 여기서 첫 번째 최솟값은 배열 전체에서 가장 작은 값이고, 두 번째 최솟값은 첫 번째 값보다 큰 수 중 가장 작은 값, 세 번째 최솟값은 두 번째 값보다 큰 수 중 가장 작은 값을 의미합니다.
이 문제는 배열의 각 요소를 한 번씩 순회하면서, 현재 요소가 첫 번째, 두 번째, 세 번째 최솟값 조건에 해당하는지 차례로 검사하는 방식으로 해결할 수 있습니다.
알고리즘 동작 원리
세 개의 변수(first, sec, third)를 각각 정수형 최댓값인 INT_MAX로 초기화한 뒤, 배열을 순회하며 다음 규칙을 적용합니다.
- 현재 요소가 first보다 작으면: third ← sec, sec ← first, first ← 현재 요소
- 그렇지 않고 현재 요소가 sec보다 작으면: third ← sec, sec ← 현재 요소
- 그렇지 않고 현재 요소가 third보다 작으면: third ← 현재 요소
이렇게 하면 기존의 작은 값들이 자동으로 한 단계씩 뒤로 밀려나면서 세 개의 최솟값이 올바르게 유지됩니다.
예제 코드
#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)로 매우 효율적입니다. 다만 중복된 값이 있을 때 같은 값이 여러 순위에 걸치지 않게 하려면 비교 조건에 등호 처리를 추가하는 등 요구 사항에 맞게 로직을 조정해야 합니다.