배열에서 n개의 가장 작은 요소를 원래 순서대로 출력하는 방법

문제 개요

k개의 요소로 구성된 배열이 주어졌을 때, 프로그램은 그중 n개의 가장 작은 요소를 찾아 원래 등장 순서 그대로 출력해야 합니다.

예를 들어 다음과 같은 입출력을 생각해 볼 수 있습니다.

입력 : arr[] = {1, 2, 4, 3, 6, 7, 8}, k=3
출력 : 1, 2, 3

여기서 k가 3이라는 것은 배열에서 가장 작은 3개의 요소를 원래 순서대로, 즉 1, 2, 3 순으로 표시해야 한다는 의미입니다.

알고리즘

START
Step 1 -> 변수 i, max, pos, j, k=4와 배열 크기 size를 선언
Step 2 -> i=k부터 i<size까지 반복
    max = arr[k-1]
    pos = k-1
    j=k-2부터 j>=0까지 감소하며 반복
        만약 arr[j]>max 라면
            max = arr[j]
            pos = j
    IF max > arr[i]
        j = pos
        j < k-1 인 동안 반복
            arr[j] = arr[j+1]
            j++
        arr[k-1] = arr[i]
    End IF
End
Step 3 -> i=0부터 i<k까지 반복하며 arr[i] 출력
STOP

예제 코드

다음은 위 알고리즘을 C 언어로 구현한 전체 예제입니다.

#include <stdio.h>
int main() {
    int arr[] = {5,8,3,1,2,9};
    int i, max, pos, j, k=4;
    int size = sizeof(arr)/sizeof(arr[0]);
    // 삽입 정렬 방식 활용, k번째 요소부터 시작
    for(i=k;i<size;i++){
        max = arr[k-1];
        pos = k-1;
        for(j=k-2;j>=0;j--) {
            if(arr[j]>max) {
                max = arr[j];
                pos = j;
            }
        }
        if ( max> arr[i] ) {
            j = pos;
            while( j < k-1 ) {
                arr[j] = arr[j+1];
                j++;
            }
            arr[k-1] = arr[i];
        }
    }
    // 앞쪽 k개의 요소 출력
    for (i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

5 3 1 2

동작 원리

이 알고리즘은 삽입 정렬의 아이디어를 응용한 방식입니다. 먼저 배열의 앞쪽 k개 요소를 임시 후보군으로 유지하고, 나머지 요소를 하나씩 검사하면서 현재 후보군의 최댓값보다 작은 값이 발견되면 해당 최댓값을 제거하고 새로운 값을 끝에 추가합니다. 이 과정을 반복하면 배열의 앞 k개 자리에는 지금까지 확인한 가장 작은 k개의 요소가 원래 순서를 유지한 채 저장됩니다. 마지막으로 앞쪽 k개만 출력하면 원하는 결과를 얻을 수 있습니다.