[ baekjoon ] #1754 듣보잡

백준 #1754 듣보잡

💡Idea(Time Exceeded)

1. N+M만큼 반복하며 N보다 작을 때 no_listen 벡터에 저장
   같거나 클 때 no_see 벡터에 저장
   no_listen → 듣도 못한 사람들, no_see → 보도 못한 사람들
2. no_listen 사람이 no_see에도 존재할 경우 answer 벡터에 저장
3. answer 벡터 size 출력
4. answer 벡터 sort(default 값이 오름차순)한 후 출력

   Source Code

   #include <iostream>
   #include <string>
   #include <vector>
   #include <algorithm>
   using namespace std;
   
   int main() {
   	int N, M;
   	vector <string> no_listen, no_see, answer;
   	cin >> N >> M;
   	for (int i = 0; i < N + M; i++) {
   		string str;
   		cin >> str;
   		if (i < N) {
   			no_listen.push_back(str);
   		}
   		else no_see.push_back(str);
   	}
   
   	for (string l : no_listen) {
   		for (string s : no_see) {
   			if (l == s) {
   				answer.push_back(s);
   				break;
   			}
   		}
   	}
   
   	cout << answer.size() << endl;
   	sort(answer.begin(), answer.end());
   
   	for (int i = 0; i < answer.size(); i++) {
   		cout << answer[i] << endl;
   	}
   	return 0;
   }

   → 위 코드를 제출한 결과 시간 초과 발생...

💡Idea

1. 듣도 못한 사람을 저장할 map<string, int>를 생성한 후 저장
   시간 초과를 해결하기 위해 자료형 map 사용 ! (검색 용이)
2. 보도 못한 사람을 입력 받으면서 map에 존재하는지 비교해서 존재하면 answer에 저장
3. answer size 출력
4. answer sort(오름차순 정렬) 후 출력

[ Source Code ]

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
	int N, M;
	string str;
	map<string, int> no_listen;
	vector <string> answer;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> str;
		no_listen.insert(make_pair(str, 1));
	}
	
	for (int i = 0; i < M; i++) {
		cin >> str;
		if (no_listen[str]) {
			answer.push_back(str);
		}
	}

	cout << answer.size() << endl;

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

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << endl;
	}
	return 0;
}

→ 이 코드를 다시 제출해보니 성공 !!!

문자열 문제를 보면 항상 string이나 vector를 사용하려고 했는데 이러한 관념 때문에 자료형 map을 사용할 생각을 하지 못함...

Feedback

1. 익숙한 자료형을 사용하는 것도 좋지만 다양한 자료형을 사용해보기 !!
2. 시간초과에 대해서도 생각해보기