[백준] 20551번 : Sort 마스터 배지훈의 후계자 (C언어 / C99)

문제

지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다. 그다음 M개의 질문을 한다. 각 질문에는 정수 D가 주어진다. 제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력하면 된다. 단, D가 B에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.

 

 

조건 및 입출력

- 첫째 줄에 배열 A의 원소의 개수 N과 질문의 개수 M이 공백으로 구분되어 주어진다.

다음 줄부터 N줄에 걸쳐 정수 A(0), A(1), ..., A(N-1)이 주어진다.

다음 줄부터 M줄에 걸쳐 정수 D가 주어진다.

-  M개의 질문에 대해서 주어진 D가 B에서 처음으로 등장한 위치를 출력한다. 단, 존재하지 않는다면 -1를 출력한다. (배열에서 가장 앞의 원소의 위치는 0이다.)

- 시간 제한: 2초 / 메모리 제한: 512MB

 

 

코드 (C99)

#include <stdio.h>

//프로토타입 선언부
void heap_sort(int heap[], int size);
int binary_search(int arr[], int size, int target);

//전역변수 선언부
int question[200000] = { 0 };

main()
{
	int test, check;
	scanf("%d %d", &test, &check);

	for (int i = 0; i < test; i++)
		scanf("%d", &question[i]);

	heap_sort(question, test);

	for (int i = 0; i < check; i++)
	{
		int find;
		scanf("%d", &find);
		
		printf("%d\n", binary_search(question, test, find));
	}
	return 0;
}

void heap_sort(int heap[], int size)
{
	for (int i = 1; i < size; i++)
	{
		int child = i;
		do
		{
			int root = (child - 1) / 2;
			if (heap[root] < heap[child])
			{
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			child = root;
		} while (child != 0);
	}

	for (int i = size - 1; i >= 0; i--)
	{
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int child = 1;
		do
		{
			child = 2 * root + 1;

			if (child < i - 1 && heap[child] < heap[child + 1])
				child++;
			if (child < i && heap[root] < heap[child])
			{
				temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			root = child;
		} while (child < i);
	}
}

int binary_search(int arr[], int size, int target)
{
	int mid, left = 0, right = size - 1;

	while (left <= right)
	{
		mid = left + (right - left) / 2;

		if (arr[mid] == target)
		{
			if (right == mid)
				break;
			right = mid;
		}
		else if (arr[mid] < target)
			left = mid + 1;
		else
			right = mid - 1;
	}
	if (arr[mid] == target)
		return mid;
	else
		return -1;
}

 

 

---

여담

처음에는 정렬하고, 이진탐색으로 구현하면 금방 맞출 수 있을 것이라 생각했다.

그러나 막상 문제를 풀어보니 중복되는 숫자가 주어지는 경우 이진 탐색을 하게 되면 제일 처음 등장하는 인덱스가 아닌 중복되는 숫자를 발견 즉시 인덱스 값을 반환한다는 것이다.

 

이를 최초 등장 인덱스 (빠른 인덱스) 를 반환하는 알고리즘으로 고칠 필요가 있었다.

그래서 이진 탐색 알고리즘을 손을 봤다.

 

몇 달을 고민하다, 결국 오늘 풀었다.

 

이진 탐색의 오른쪽 값이 중단 값이랑 같아지면 오른쪽에는 더 이상 중복되는 숫자가 없거나 그 보다 큰 수만 있으니 최소 인덱스를 찾을 수 있게 된다.

 

그렇게 코드를 수정하면 된다. 나머지는 일반 이진 탐색 알고리즘과 동일하다.

끝으로, 만약 배열에 해당 값이 없으면 -1을 반환하면 된다.

 

아이고.. 어렵다. 어려워...