[자습] 다음 입사문제 중에서 - 001

1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오.(단 점들의 배열은 모두 정렬되어있다고 가정한다.)

S = {1, 3, 4, 8, 13, 17, 20}이 주어졌다면 결과값은 (3, 4)가 될 것이다.

가장 거리가 짧다란 이야기는 두 점의 뺀 값이 최소값이란 이야기 일 것이다.

그렇담...

1. 1. 두개의 반복문을 이용하여 각각의 점들간의 거리차를 구한다.


2. 2. 값을 저장 하였다가 새로운 값이 그 값보다 작으면 대체한다.


3. 3. ... 고민좀 해보자...

objective-C

#import <Cocoa/Cocoa.h>

int main(int argc, const char * argv[]) {

    int S[7]={1, 3, 4, 8, 13, 17, 20}, temp_result, i, j, result, result_i, result_j;

    result = 1000;



    for (i = 0; i <= 5; i = i + 1) {

        for (j = i + 1; j <= 6 ; j = j + 1) {

            temp_result = abs(S[i] - S[j]);

            if (result > temp_result) {

                result = temp_result;

                result_i = S[i];

                result_j = S[j];

            }

        }

    }



    printf("가장 거리가 짧은 점들은 (%d, %d)", result_i, result_j);



    return NSApplicationMain(argc, argv);

}

가장 거리가 짧은 점들은 (3, 4)

흐~ㅁ 근데 문제는 문제를 해결할 함수를 만들어라~인데 걍 풀어버렸네... 쩝...

[때구니™]

입사 시험이 이정도였으면 좋았을텐데
모 회사는... ㅎㄷㄷ

[Rey_Mysterio]

'점들의 배열은 모두 정렬되어있다고 가정한다' 가 힌트 아닐까요?
반복문 한번으로 구할 수 있을꺼 같네요
(n+1) - n = 최저인 인덱스를 저장하면 될듯

[호노위스]

For loop 에서 break 를 적절히 써 주시면 조금더 연산이 빨리질 수 있겠네요

[Ein_]

더블루프를 쓰면 O(n^2) 이라서 점수를 받을 수 없는 문제입니다. O(n) 안에 해결해야 하는 문제고 리커시브하게 풀어내면 추가 배점이 있을거같네요.(호불호는 있지만 코딩 스킬을 보는거라면요.)

[雪風 Maive]

함수를 만드는 것이라서 재귀쓰면 안되지 않나요?
입력값 무한대로 가정해야 하니...

[aksiz]

처음 두개의 수(나중에 return을 위해)와 그 거리하고, 맨 처음 수를 뺀 나머지 리스트를 받는 helper 함수 하나 만들면 되죠. 정식 함수에는 리스트 하나 받아서 적절한 계산 후에 helper만 호출하는 식으로요.

함수가 어떤걸 변수로 받아야 하는지를 안알려줘서 다른 방식으로도 가능 하겠지만, 일단 리스트 하나만 받는다고 가정하고 짜면 저렇죠. (다만 helper 없이 하는거면 언어에 따라서 재귀로는 힘들지도)

[aksiz]

걍 더블루프 쓰지말고, 루프 돌리기 전에 초기 result 를 첫 두수의 거리로, result_i=첫번째 수, result_j=두번째 수로 둔 뒤에, loop문 한번 돌리고 바로 result_i, result_j 리턴하면 됩니다.
다만 루프 돌릴때, i나 i+1이 리스트 크기를 넘지 않도록 주의해야 하고요.