백준 1764번 : 듣보잡

문제 링크 : www.acmicpc.net/problem/1764

풀이에 참고한 링크 : zerobell.tistory.com/9   blockdmask.tistory.com/178

내 풀이 (2020.12.21.) :

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

using namespace std;

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

	vector<string> not_heard;
	vector<string> not_seen;

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string str; cin >> str;
		not_heard.push_back(str);
	}
	for (int i = 0; i < M; i++) {
		string str; cin >> str;
		not_seen.push_back(str);
	}

	vector<string> not_heard_seen;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (not_heard.at(i) == not_seen.at(j)) {
				not_heard_seen.push_back(not_seen.at(j));
			}
		}
	}
	
	sort(not_heard_seen.begin(), not_heard_seen.end()); // 사전 순 정렬

	cout << not_heard_seen.size() << endl;
	for (int i = 0; i < not_heard_seen.size(); i++) {
		printf("%s\n", not_heard_seen.at(i).c_str());
	}

	return 0;
}

결과 : 시간 초과

O(N x M) = O(50,0000 x 50,0000) = O(2500,0000,0000)

 

알게된 점 :

 - printf로 string을 출력할 때는 .c_str()을 통해 char 배열 형태로 형변환을 해줘야 한다.

 - string vector의 사전 순 정렬은 sort(v.begin(), v.end()); 로 한다.

---

내 풀이2 (2020.12.21.) :

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

using namespace std;

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

	vector<string> not_heard_seen;

	int N, M; cin >> N >> M;
	for (int i = 0; i < N + M; i++) {
		string str; cin >> str;
		not_heard_seen.push_back(str);
	}
	sort(not_heard_seen.begin(), not_heard_seen.end()); // 사전 순 정렬

	vector<string> duplicate;

	for (int i = 0; i < N + M - 1; i++) {
		if (not_heard_seen.at(i) == not_heard_seen.at(i + 1)) {
			duplicate.push_back(not_heard_seen.at(i));
		}
	}

	cout << duplicate.size() << endl;
	for (int i = 0; i < duplicate.size(); i++) {
		printf("%s\n", duplicate.at(i).c_str());
	}

	return 0;
}

결과 : 성공

 

풀이 :

애초에 듣지 못한 명단과 보지 못한 명단을 따로 관리하지 말고

모두 하나의 벡터에 넣고 사전 순으로 정렬하면

듣보잡은 벡터 상에서 서로 붙어 있을 것이다.

 

sort 함수는 quick sort 기반으로 평균 O(nlogn) 최악 O(n^2)이다.

따라서 시간복잡도는 O((N+M)log(N+M)) = O(100,0000*log(100,0000)) = O(600,0000)