[C++] 백준 4158: CD

문제

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

4158번: CD

 

해결 방법

1. 상근이가 가지고 있는 CD의 번호를 모두 vector에 저장한다.

2. 선영이가 가지고 있는 CD의 번호를 하나씩 입력받고 이분탐색을 진행한다.

3. left는 0, right는 상근이가 가진 CD의 개수-1 이며 mid를 구해 vector[mid]와 선영이의 CD를 비교하며 같은 번호의 개수를 구한다.

 

코드

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

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

	int a, b, x;

	while (true) {
		int cnt = 0;
		vector<int>v;

		cin >> a >> b;

		if (a == 0 && b == 0)
			break;

		for (int i = 0; i < a; i++) {
			cin >> x;

			v.push_back(x);
		}

		for (int i = 0; i < b; i++) {
			cin >> x;

			int left = 0;
			int right = a - 1;

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

				if (v[mid] == x) {
					cnt++;
					break;
				}
				else if (v[mid] > x) {
					right = mid - 1;
				}
				else {
					left = mid + 1;
				}

			}
		}

		cout << cnt << '\n';
	}
}