[백준 1764] 듣보잡

난이도

실버 IV

📜문제

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

🌞그냥 문자열 비교 풀이

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

using namespace std;

int main()
{
	int N = 0, M = 0;
	cin >> N >> M;

	vector<string> v(N + M);
	vector<string> ans;

	for (int i = 0; i < N + M; i++)
	{
		cin >> v[i];
	}

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

	int answer = 0;
	for (int i = 0; i < N + M - 1; i++)
	{
		if (v[i] == v[i + 1]) // 정렬을 했을때 2개가 있는 경우
		{
			ans.push_back(v[i]);
			answer++;
			i++;
		}
	}
	cout << answer << "\n";
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << "\n";

	return 0;
}

맨처음에 단순하게 생각해서 Vector에 다 넣은 다음 정렬을 해서 2개가 붙어있는 경우만을 출력했다.
이것은 운좋게 맞았고 입력이 더 많았다면 시간초과가 났을수도 있을 것 같다.

🌞이진탐색 풀이

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

using namespace std;

int main()
{
	int N = 0, M = 0;
	cin >> N >> M;

	vector<string> v(N);
	vector<string> ans;

	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	string name = "";
	for (int i = 0; i < M; i++)
	{
		cin >> name;
		if (binary_search(v.begin(), v.end(), name)) // 이진 탐색으로 name이 있으면 true
		{
			ans.push_back(name);
		}
	}
	sort(ans.begin(), ans.end()); // 사전순 출력을 위한 정렬

	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << "\n";

	return 0;
}

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기