C++ 배열에서 최솟값과 두 번째로 작은 값 찾는 방법

크기가 n인 배열이 주어졌을 때, 배열에서 가장 작은 요소(최솟값)와 두 번째로 작은 요소를 찾아야 합니다. 여기서 첫 번째로 작은 값은 배열의 최솟값이고, 두 번째로 작은 값은 최솟값보다 크면서 그다음으로 작은 값을 의미합니다.

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

알고리즘 동작 원리

두 개의 변수 first와 sec를 각각 정수형 최댓값(INT_MAX)으로 초기화한 뒤, 배열을 순회하며 다음 규칙을 적용합니다.

• 현재 요소가 first보다 작으면, 기존의 first 값을 sec에 저장하고 현재 요소를 새로운 first로 갱신합니다.
• 그렇지 않고 현재 요소가 sec보다 작으면, 현재 요소를 sec으로 갱신합니다.

이 방식은 배열을 단 한 번만 순회하므로 시간 복잡도가 O(n)으로 매우 효율적입니다.

예제 코드

#include<iostream>
using namespace std;
int getTwoSmallest(int arr[], int n) {
    int first = INT_MAX, sec = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (arr[i] < first) {
            sec = first;
            first = arr[i];
        } else if (arr[i] < sec) {
            sec = arr[i];
        }
    }
    cout << "First smallest = " << first << endl;
    cout << "Second smallest = " << sec << endl;
}
int main() {
    int array[] = {4, 9, 18, 32, 12};
    int n = sizeof(array) / sizeof(array[0]);
    getTwoSmallest(array, n);
}

실행 결과

First smallest = 4
Second smallest = 9

코드 설명

위 예제에서 배열 {4, 9, 18, 32, 12}를 순회하면, 가장 먼저 4가 first에 저장됩니다. 이후 9는 first보다 크지만 sec(INT_MAX)보다 작으므로 sec에 저장됩니다. 나머지 요소들(18, 32, 12)은 두 조건 모두 만족하지 않으므로 그대로 유지됩니다. 최종적으로 최솟값 4와 두 번째로 작은 값 9가 출력됩니다.

참고로 중복된 최솟값이 존재하는 경우(예: {4, 4, 9}) 위 코드는 두 번째로 작은 값을 4로 반환할 수 있습니다. 엄격하게 서로 다른 값을 원한다면 조건에 arr[i] != first를 추가하여 처리할 수 있습니다.