| 문제
입력(표준 입력)
첫번째 줄에, 입력할 숫자들의 개수 N와 정수 k를 입력합니다.
다음줄 부터 N개의 줄만큼, 각각의 줄마다 하나의 입력 변수를 입력해야 합니다.
출력(표준 출력)
첫 번째 줄에는, 내림차순으로 가장 큰 k개의 원소들을 출력해 냅니다.
두 번째 줄에는, 가장 큰 k 원소들을 추출해낸 후에 힙을 출력해 냅니다.
ex)
입력 | 출력 |
10 4 16 14 10 8 7 9 3 2 4 1 | 16 14 10 9 8 7 3 4 2 1 |
| 소스 코드
#include <stdio.h>
void array_swap(int * arr, int a, int b)
{
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void Heapify(int * arr, int parent_position, int heap_size)
{
int left, right, largest;
left=2*parent_position+1;
right=2*parent_position+2;
if((left<heap_size)&&(arr[left]>arr[parent_position]))
largest = left;
else
largest = parent_position;
if((right<heap_size)&&(arr[right]>arr[largest]))
largest = right;
if(largest != parent_position)
{
array_swap(arr, parent_position, largest);
Heapify(arr, largest, heap_size);
}
}
void Build_Heap(int * arr, int length)
{
int parent_position;
for(parent_position=length/2-1; parent_position>=0; parent_position--)
Heapify(arr, parent_position, length);
}
void Heap_Sort(int * arr, int length, int k)
{
Build_Heap(arr, length);
int last_row;
int count = 0;
for(last_row = length-1; last_row>0; last_row--)
{
if(count == k)
break;
array_swap(arr, 0, last_row);
length--;
count ++;
Heapify(arr, 0, length);
}
}
int main(void)
{
int arr[100000];
int length = 10;
int N, k, i;
// input
scanf("%d %d", &N, &k);
for(i=0; i<N; i++)
{
scanf("%d", &arr[i]);
}
Heap_Sort(arr, N, k);
// output
for(i=N-1; i>(N-1)-k; i--)
printf("%d ", arr[i]);
printf("\n");
for(i=0; i<=(N-1)-k; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}'컴퓨터 프로그래밍' 카테고리의 다른 글
| 알고리즘 - Connected Component (0) | 2014.02.15 |
|---|---|
| 알고리즘 - Priority Queue(우선순위 큐를 구현하라) (0) | 2014.02.15 |
| 알고리즘 - DFS(Depth-First Search) 깊이 우선 탐색 소스 코드 (0) | 2014.02.15 |
| ADC 모듈을 이용해서 측정한 광전압에 따라 반응하기 소스 코드 (HBE-MCU-All in One) (0) | 2014.02.15 |
| EEPROM을 이용한 비밀번호 시스템 만들기 소스 코드 공개 (HBE-MCU-All in One) (0) | 2014.02.15 |