본문 바로가기
개발/알고리즘문제

다음 입사문제

by 사과잼빵 2015. 3. 21.

[문제]

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