백준 1764번 [듣보잡] 해결하기(C++)

백준 1764: 듣보잡 [실버4]

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

 

✍️Point : 범위를 확인하기

만약 다음과 같이 아무 생각 없이 이중 for문으로 풀게 된다면, 시간 초과를 마주할 수 있다. 

??? : 배열로 입력 받고, 교집합이 있는지 이중 for문으로 확인하면 되지 않을까?

#include<bits/stdc++.h>
using namespace std;

int n,m;
string s;
vector<string>nlisten;
vector<string>nsee;
vector<string>ret;

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>s;
		nlisten.push_back(s);
	}
	
	for(int i=0;i<m;i++){
		cin>>s;
		nsee.push_back(s);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(nlisten[i]==nsee[j]){
				ret.push_back(nlisten[i]);break;
			}
		}
	}
    cout<<ret.size()<<"\n";
	for(string s: ret){
		cout<<s<<"\n";
	}
	
}

 

그 이유는, 당연하게도 n과 m의 최대가 50만이기 때문이다.

위 코드의 시간 복잡도는 O(n*m) 이므로, 최악의 경우 25억번의 연산을 수행하게 된다.

1초=1억번이라고 단순하게 생각하면, 25초라는 무시무시한 수가 나온다. 애초에 1억이 넘어가면 이 방식은 뒤로 빼야 한다.

 

💡해결

💡Idea : set 자료구조를 활용하자!

 

set 이란?
집합이라는 의미를 가지며, 중복을 허용하지 않는 고유한 값을 저장하는 순열 자료구조이다.

 

set 자료구조에는 insert, find 함수를 활용할 수 있다.

set.insert(s) : set에 s를 삽입한다.
set.find(s) : set에 s가 존재하면 그 값을 가리키는 "반복자"를 반환한다. 존재하지 않으면, set.end()를 반환한다.

 

따라서 다음과 같이 작성하면 시간 복잡도가 확 줄어든다.

#include<bits/stdc++.h>
using namespace std;

int n,m;
string s;
set<string>nlisten; // 듣도 못한
set<string>nsee; // 보도 못한
vector<string>ret; // 교집합

int main(){
	cin>>n>>m;
	// 듣도 못한 사람 입력 
	for(int i=0;i<n;i++){
		cin>>s;
		nlisten.insert(s);
	}
	
	for(int i=0;i<m;i++){
		cin>>s;// 보도 못한 사람 입력 
		if(nlisten.find(s)!=nlisten.end()){// 듣도 못한 사람에 보도 못한 사람이 있으면 
			ret.push_back(s);// 교집합 vector에 저장 
		}
	}
	sort(ret.begin(),ret.end());// 사전순 정렬 
	cout<<ret.size()<<"\n"; // 교집합 크기 출력 
	for(string s: ret){
		cout<<s<<"\n"; //교집합 요소 모두 출력 
	}
	return 0;
}

 

⌛시간 복잡도

기존의 O(n*m), 즉 N^2 의 시간복잡도, 즉 25억번의 연산에서,

 

1. set에 nlisten 삽입 (O(n))

• std::set은 내부적으로 정렬된 이진 탐색 트리로 구현되어 있다.
• 삽입(insert) 연산의 시간 복잡도는 O(log n).
• 따라서, nlisten 리스트의 모든 값을 set에 삽입하는 데 걸리는 시간은:
  • n개의 요소를 각각 삽입 → O(n * log n)

하지만 **해시 기반의 unordered_set**을 사용하면 삽입이 O(1) 시간에 수행된다. 그러면 삽입 연산의 총 시간 복잡도는:

• O(n).

2. nsee의 값을 set에서 탐색 (O(m))

• nsee 리스트의 각 값을 set에서 탐색.
• find 연산의 시간 복잡도는 O(log n) (트리 기반) 또는 O(1) (해시 기반)이다.
• 따라서, m개의 요소를 탐색하는 데 걸리는 시간은:
  • 트리 기반: O(m * log n).
  • 해시 기반: O(m).

최종 시간 복잡도

• 트리 기반 set:
  • 삽입: O(n * log n)
  • 탐색: O(m * log n)
  • 총합: O((n + m) * log n).
• 해시 기반 unordered_set:
  • 삽입: O(n)
  • 탐색: O(m)
  • 총합: O(n + m).

성공!!