이 글에서는 주어진 복잡도 제약 조건(배열 단일 순회, O(n)) 안에서 n개의 요소 중 두 번째로 작은 값을 찾는 C++ 프로그램을 소개합니다. 최솟값과 두 번째 최솟값을 한 번의 반복으로 동시에 추적하는 방식으로 문제를 효율적으로 해결할 수 있습니다.
알고리즘
Begin
function SecondSmallest() :
/* 이 함수의 인수:
포인터 배열 a
요소의 개수 n
*/
// 함수 본문:
가장 작은 수를 추적하는 변수 s1 선언
두 번째로 작은 수를 추적하는 변수 s2 선언
s1과 s2를 모두 INT_MAX로 초기화
반복문을 사용해 데이터 배열을 순회
현재 배열 요소가 s1보다 작으면,
s2 = s1, s1 = 현재 배열 요소
그렇지 않고 배열 요소가 s1과 s2 사이에 있으면,
s2 = 현재 배열 요소
if(s2 == INT_MAX)
"두 번째로 작은 요소가 없습니다" 출력
else
s2를 두 번째로 작은 요소로 출력
End
예제 코드
#include<iostream>
#include <climits> //INT_MAX를 사용하기 위한 헤더
using namespace std;
int SecondSmallest(int *a, int n) {
int s1, s2, i, t;
//s1과 s2 초기화
s1 = INT_MAX;
s2 = INT_MAX;
for(i = 0; i < n; i++) {
//현재 요소가 s1보다 작은 경우
if(s1 > a[i]) {
//s1과 s2를 함께 갱신
s2 = s1;
s1 = a[i];
}
//a[i]가 s1과 s2 사이에 있는 경우
else if(s2 > a[i] && a[i] != s1) {
//s2만 갱신
s2 = a[i];
}
}
if(s2 == INT_MAX)
cout << "두 번째로 작은 요소가 존재하지 않습니다";
else
cout << "두 번째로 작은 요소는: " << s2;
}
int main() {
int n, i;
cout << "요소의 개수를 입력하세요: ";
cin >> n;
int array[n];
for(i = 0; i < n; i++) {
cout << i + 1 << "번째 요소를 입력하세요: ";
cin >> array[i];
}
SecondSmallest(array, n); //함수 호출
return 0;
}
실행 결과
요소의 개수를 입력하세요: 5 1번째 요소를 입력하세요: 1 2번째 요소를 입력하세요: 2 3번째 요소를 입력하세요: 1 4번째 요소를 입력하세요: 3 5번째 요소를 입력하세요: 4 두 번째로 작은 요소는: 2
동작 원리와 시간 복잡도
이 알고리즘은 배열 전체를 단 한 번만 순회하므로 시간 복잡도는 O(n)이며, s1과 s2라는 두 개의 변수만 추가로 사용하므로 공간 복잡도는 O(1)입니다. 따라서 주어진 복잡도 제약 조건을 만족합니다.
핵심 로직은 다음과 같이 정리할 수 있습니다.
- 현재 요소가 s1보다 작은 경우: 기존의 s1 값이 두 번째로 작은 값의 후보가 되므로, s2를 기존 s1 값으로 갱신한 뒤 s1을 현재 요소로 바꿉니다.
- 현재 요소가 s1 이상이면서 s2보다 작은 경우: s2만 현재 요소로 갱신합니다.
조건 a[i] != s1이 필요한 이유는 중복된 최솟값이 있을 때(예: 1, 1, 2, 3) 동일한 값이 두 번째로 작은 값으로 잘못 선택되는 것을 막기 위해서입니다. 모든 요소가 같은 값이라면 s2는 끝까지 INT_MAX로 남으므로, 프로그램은 "두 번째로 작은 요소가 존재하지 않는다"고 알려줍니다.
참고로 예제의 int array[n]처럼 크기를 실행 시점에 정하는 가변 길이 배열(VLA)은 표준 C++ 사양에는 포함되어 있지 않고 일부 컴파일러에서만 지원됩니다. 이식성을 높이려면 std::vector<int>를 사용하는 것이 좋습니다.