1920 - 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

제가 알고리즘 문제 풀 때 항상 약했던 부분이 이분 탐색이라서 백준 이분 탐색 문제를 재미삼아 풀어봤습니다.

 

간단합니다. 처음 N개의 배열을 정렬하고 M개의 배열을 하나씩 뽑아서 이분 탐색을 시켜서 있으면 1을 출력하고 없으면 0을 출력하면 됩니다.

 

#include <stdio.h>
#include <malloc.h>

void swap(int* arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int partition(int* arr, int left, int right) {
	int pivot = arr[left];
	int low = left + 1;
	int high = right;

	while (low <= high) {
		while (pivot >= arr[low] && low <= right) {
			low++;
		}
		while (pivot <= arr[high] && high >= left + 1) {
			high--;
		}
		
		if (low <= high) swap(arr, low, high);
	}

	swap(arr, left, high);
	return high;
}

void quickSort(int* arr, int left, int right) {
	if (left <= right) {
		int mid = partition(arr, left, right);
		quickSort(arr, left, mid - 1);
		quickSort(arr, mid + 1, right);
	}
}

int binarySearch(int* arr, int target, int left, int right) {
	int mid = (left + right) / 2;
	if (arr[mid] == target) return 1;
	if (left > right) return 0;
	if (arr[mid] > target) {
		return binarySearch(arr, target, left, mid- 1);
	}
	else {
		return binarySearch(arr, target, mid + 1, right);
	}
}

int main(void) {
	int N;
	scanf("%d", &N);
	int* arr1 = (int*)malloc(sizeof(int) * N);
	for (int n = 0; n < N; n++) {
		scanf("%d", &arr1[n]);
	}
	quickSort(arr1, 0, N - 1);
	int M;
	scanf("%d", &M);
	int* arr2 = (int*)malloc(sizeof(int) * M);
	for (int m = 0; m < M; m++) {
		scanf("%d", &arr2[m]);
	}
	for (int m = 0; m < M; m++) {
		if (binarySearch(arr1, arr2[m], 0, N - 1)) {
			printf("1\n");
		}
		else {
			printf("0\n");
		}
	}
}

이 간단한 문제를 제가 왜 포스팅을 하냐면 제가 5달 전에 똑같이 문제를 푼 게 있길래 확인해보니 코드 길이가 이상하게 짧더군요. 그래서 제가 쓴 코드를 보니까...

 

이상하게 풀었더라고요 ?

 

#include <stdio.h>
#define num 10007;

int main(void) {
	int N, M;
	scanf("%d", &N);
	int temp, temp2;

	int arr[10007][50];
	
	for (int i = 0; i < 10007; ++i) {
		for (int j = 0; j < 50; ++j) {
			if (j == 0) {
				arr[i][j] = 1;
			}
			else arr[i][j] = 0xffffff;
		}
	}

	for (int i = 0; i < N; ++i) {
		scanf("%d", &temp);
		temp2 = temp % 10007;

		if (temp2 < 0) {
			temp2 *= -1;
		}
		arr[temp2][arr[temp2][0]] = temp;
		arr[temp2][0] += 1;
	}
	
	int tf;
	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
		scanf("%d", &temp);
		temp2 = temp % 10007;
		tf = 1;
		if (temp2 < 0) {
			temp2 *= -1;
		}
		
		for (int j = 1; j < 50; ++j) {
			if (arr[temp2][j] == temp) {
				printf("1\n");
				tf = 0;
				break;
			}
		}
		
		if (tf == 1) {
			printf("0\n");
		}
	}
}

아마 해쉬 맵? 해쉬 테이블? (제가 아직 해쉬를 정확하게 공부를 안했기에 어떤 방법인지는 모르겠습니다)를 써서 푼 거 같은데

 

엄... 이분 탐색을 아예 안 썼습니다.

 

단지, N개의 숫자들을 전부 다 받아와서 해쉬를 만들고 M개의 숫자를 순회하면서 있는 지 없는 지 파악을 한 거 같습니다.

 

제가 짠 코드인데도 오랜만에 보니 색다르게 느껴지네요 ㅋㅋ

 

근데 아마 밑에 코드는 (5달 전에 짠 코드) Edge Case가 분명 존재할 거 같다만, 운 좋게 통과한거 같습니다.

 

해쉬 공부의 필요성이 느껴지네요.

---

이상 1920 - 수 찾기였습니다. ^_^