[BAEKJOON] 1920번 : 수 찾기

문 제

 

소 스  코 드

#include<iostream>
#include<algorithm>

void SearchNumber();
bool SearchIndex(int *, const int&, const int&);

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	SearchNumber();
}

void SearchNumber() {
	// input N
	int N;
	std::cin >> N;

	// Sort & Arr
	int *numbers{ new int[N] };
	for (int i = 0; i < N; ++i) std::cin >> numbers[i];
	std::sort(numbers, &numbers[N]);

	int temp, num;
	std::cin >> temp;
	for (int i = 0; i < temp; ++i) {
		std::cin >> num;
		std::cout << SearchIndex(numbers, N, num) << '\n';
	}
	delete[] numbers;
}

bool SearchIndex(int * arr, const int& n, const int& num) {
	int left{ 0 }, right{ n - 1 }, mid;
	if ((num < arr[left])||(num > arr[right])) return false;
	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] == num) return true;
		else if (arr[mid] > num) right = mid - 1;
		else					 left = mid + 1;
	}
	return false;
}

 

풀 이

 

• 이진 탐색을 통하여 구현.

배열이 오름차순이나 내림차순으로 정렬이 되어 있어야 적용이 가능하다.

N : 5 , arr[5] = { 4, 1, 5, 2, 3 }  4을 찾는다면,

먼저 배열을 오름차순으로 정렬한다. Algorithm Sort

arr[5] = { 1, 2, 3, 4, 5 }

 

left = 0, right = n - 1, mid = ( left + right ) / 2

arr[mid] < 4 임으로 left = mid + 1 = 3이 된다.

 

left = 3, right = 4, mid = (3 + 4) / 2 = 3이 된다.

arr[3] == 4이기 때문에 4는 arr배열에 존재한다.

 

• STL Map 컨테이너를 이용한 간단한 구현.

#include<iostream>
#include<map>

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::map<int, int> numbers;
	int N, temp;

	std::cin >> N;

	int num;
	for (int i = 0; i < N; ++i) {
		std::cin >> num;
		numbers[num] = 1;
	}

	std::cin >> temp;

	for (int i = 0; i < temp; ++i) {
		std::cin >> num;

		std::cout << numbers[num] << '\n';
	}
}

 

출 력 값

 

 

 

문 제  출 처

문제 링크 :