주어진 integer array에서 두번째로 작은 수(second smallest)를 구하여 보자. 일단 n개의 원소를 가진 정렬되지 않은 배열에서 가장 작은 값을 찾기 위해서는 n개 모두를 한 번은 살펴보아야 한다. O(n). 단순 무식한 방법으로 n개를 모두 살펴보면서 가장 큰 수를 찾아 제거하고, 다시 한 번 n-1를 찾아서 가장 큰 수를 출력하면 된다. 전체를 정렬하고 찾으려면 O(nlgn)이 들기 때문에 오히려 더 비효율적이다. (comparison based sort - 비교 기반 정렬)
배열의 원소가 적어도 2개 이상이라는 전제 하에, 아래 소스는 모든 원소를 두 번 읽지는 않고 한 번만 읽고 두번째로 작은 원소를 출력한다. 다만, 두번째로 작은 수가 아니라 임의의 i번째의 경우 이 방법은 사용할 수 없다. 이럴 경우에는 randomized selection을 써야 O(n)에 가능하다.
#include <iostream>
using namespace std;
main() {
int a[] = {3, 1, 10, 34, 5, 3};
int len = sizeof(a)/sizeof(int);
for (int i = 1; i < len; i++) {
if (a[i] <= a[0]) {
a[1] = a[0];
a[0] = a[i];
} else if (a[i] < a[1]) {
a[1] = a[i];
}
}
cout << a[1] << endl;
}그런데, 뭔가 더 좋은 방법이 있지 않을까?
'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글
| [CS] 비트 매스크(Bit Mask) (2) | 2010/02/21 |
|---|---|
| [CS] 반복되지 않는 첫번째 문자를 찾아라 (3) | 2010/02/19 |
| [CS] 16진수를 10진수로 바꾸어보자 (0) | 2010/02/18 |
| [CS] 배열에서 두번째로 작은 수를 구하기 (2) | 2010/02/18 |
| [CS] c++에서 실수형 처리 (0) | 2010/02/12 |
