글 읽기 - 반례가 있을까요?

kellyyaa 1년 전 0

집합을 각각 받고 서로를 비교한 뒤 겹치는 값을 각 벡터의 크기에서 빼주는 식으로 해봤는데

예제는 맞고 여러가지 넣어봤는데 어디서 틀린건지 모르겠네요ㅠㅠ 뭐가 문제인지 봐주시면 감사하겠습니다!

#include <iostream>
#include <vector>
using namespace std;
vector<int> an;
vector<int> bm;
int n, m, num, res1, res2;

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> num;
		an.push_back(num);
	}
	for (int i = 0; i < m; i++) {
		cin >> num;
		bm.push_back(num);
	}
	
	for (int i = 0; i < m; i++) {
	int left = 0;
	int right = n - 1;
		int t = bm[i];
		while (left <= right) {
		int mid = (left + right) / 2;
			if (an[mid] == t) {
				res1++;
				break;
			}
			else if (t < an[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
	}
	for (int i = 0; i < n; i++) {
		int left = 0;
		int right = m - 1;
		int t = an[i];
		while (left <= right) {
		int mid = (left + right) / 2;
			if (bm[mid] == t) {
				res2++;
				break;
			}
			else if (t < bm[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
	}
	cout << an.size() - res1 + bm.size() - res2; 
}

mckkk119 1년 전 0

이분 탐색은 해당 배열이 정렬되어 있을 때만 사용이 가능합니다.

예제 입력에서는 각 집합의 원소들이 정렬된 형태로 주어졌지만

실제 테스트 케이스에서는 정렬되지 않은 데이터가 존재할 수도 있습니다.

kellyyaa 1년 전 0

당연히 정렬된 값만 생각했네요 해결했습니다! 감사합니다:)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있을까요?

kellyyaa 1년 전 0

mckkk119 1년 전 0

kellyyaa 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말