[문제]
1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오. (단 점들의 배열은 모두 정렬되어있다고 가정한다.)
예를들어 S={1, 3, 4, 8, 13, 17, 20} 이 주어졌다면, 결과값은 (3, 4)가 될 것이다.
[풀이]
순차 탐색 방법으로 풀 수 있다.
#include <iostream>
using namespace std;
void FindShort(int _testArr[])
{
int iIdx = 1;
int iSize = _testArr[1]- _testArr[0]; //최소 2개의 점은 있다고 가정
for(int i = iIdx; i< sizeof(_testArr) / sizeof(int) - 1; ++i)
{
if(iSize > _testArr[i+1] - _testArr[i])
{
iIdx = i;
iSize = _testArr[i+1] - _testArr[i];
}
}
cout<<'('<<_testArr[iIdx]<<','<<_testArr[iIdx+1]<<')'<<endl;
}
void main(void)
{
int testArr[] = {1, 3, 4, 8, 13, 17, 20};
FindShort(testArr);
}
'개발 > 알고리즘문제' 카테고리의 다른 글
알고스팟-URIDecoding (0) | 2015.07.23 |
---|