[C++] 백준 10815번 숫자 카드

1. 문제이해

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

10815번: 숫자 카드

 

상근이가 가지고 있는 숫자 카드의 개수(N)와 각 숫자카드에 적힌 숫자를 입력받는다.

이어서 정수 M과 M개의 숫자들을 입력받는다.

M개의 수들에 대해 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1, 아니면 0을 출력한다.

 

 

 

2. 문제풀이

 

N과 M의 범위는 무난하지만, 입력받는 숫자의 범위가 꽤나 크다.  (-10,000,000 <=  x <= 10,000,000)

하나씩 비교하면 시간초과가 발생한다. 이분탐색으로 풀이해야 하는 문제이다.

 

이분탐색은 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

구하고자 하는 값을 배열의 중간값(mid)과 비교하여,

중간값보다 작으면 좌측(end = mid - 1)으로, 크면 우측으로 다시 탐색(start = mid + 1)하는 방식이다.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <long long> sang;

// 이분 탐색
int search(int start, int end, long long num) {
	while (start <= end) {
		int mid = (start + end) / 2;

		// 상근이가 가진 번호와 일치하면 1 리턴
		if (sang[mid] == num) {
			return 1;
		}
		else if(sang[mid] > num) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}

	// 상근이가 가진 번호와 일치하는 것이 없으면 0 리턴
	return 0;
}

int main() {
	int N, M;
	long long element;

	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> element;
		sang.push_back(element);
	}

	sort(sang.begin(), sang.end());

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> element;
		cout << search(0, N - 1, element) << " ";
	}

	return 0;
}

이분 탐색을 이용해 상근이가 가진 숫자들 중 매개변수로 받은 num과 같은 숫자를 찾는 search 함수를 구현했다.

num값과 snag[mid] 값을 비교하여

sang[mid] > num 인 경우 end = mid - 1 해서 재탐색,

sang[mid] < num 인 경우 start = mid + 1 해서 재탐색한다.

만약 상근이가 가진 숫자 중 매개변수로 받은 num이 존재한다면, 1을 리턴 후 함수를 종료한다.

만약 while 문이 종료되고, 상근이가 가진 숫자 중 num이 없다면, 0을 리턴 후 종료한다.

 

메인 함수에서는 상근이가 가진 숫자카드의 개수(N)과 각 숫자들(vector <long long> sang)을 입력받는다.

이분탐색을 위해 상근이가 가진 숫자들을 차례로 정렬하고,

M개의 숫자들을 입력받아, 각 숫자들에 대해 이분탐색을 진행, 출력한다.

 

 

---

이분탐색 문제에 약해서 이분탐색 위주로 공부중이다.

뭔가 비슷한 문제들인듯 하면서도 아직은 어렵다..😥

익숙하지 않아서 그렇겠지만, 쓰는게 매끄러워질때까지 연습해야겠다.💪

 

문제에 대한 지적이나 질문은 언제나 감사하게 받고있습니다.😊