글 읽기 - 반례를 못찾겠습니다.

snstfka02 3년 전 0

set의 insert특성을 이용해서 시간복잡도 O(N)에 해결해보려고 했습니다.

N개의 듣도못한 사람을 먼저 넣어두고

M개의 보도못한 사람을 입력받을때 이미 존재하는 것을 insert했을때 pair을 통해 false를 받고

이 사람은 듣도보도못한사람이 되므로 answer 벡터에 추가했습니다.

혹시 이렇게 작성하였을시 시간복잡도가 O(N)이 맞는지.

그리고 반례를 알려주시면 정말 감사하겠습니다.

#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
	set<string> a;
	vector<string> answer;
	int N, M;
	cin >> N >> M;

	//O(n) ? 
	for (int i = 0; i < N + M; i++) {
		string temp;
		cin >> temp;
		pair<set<string>::iterator, bool> pr;	//insert의 결과를 받을 pair
		pr = a.insert(temp);

		if (pr.second == false) {	//만약 이미 존재하는 사람을 넣었다면 이 사람은 듣도보도못한 사람이다. 즉 답에 포함
			answer.push_back(temp);
		}
	}

	cout << answer.size() << endl;
	vector<string>::iterator it = answer.begin();
	for (it; it != answer.end(); it++) cout << *it << endl;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

snstfka02 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말