✅ map

문제

링크

풀이

1. 문제 접근

듣도 못한 사람과 보도 못한 사람이 각 N, M 명씩 주어지므로
이중에서 중복되는 사람을 구해주면 된다.
배열에 저장해서 찾아도 되지만 N, M의 범위가 500,000 이하의 자연수로 굉장히 크므로
일반적인 방법으로는 풀기 힘들다는 생각이 든다.

2. 자료구조 선택과 그 이유

map을 사용하여 이름과 불린 횟수를 저장하여 찾는 것이 탐색 속도에서 유리하다고 생각된다.

3. 문제 해결 로직 (풀이법)

map을 사용하여 key에는 이름을, value에는 불린 횟수를 저장하여 value가 2이상인 key를 찾는다.

의사코드

map<string, int>
 
cin >> N >> M
for(i : 1 ~ N+M){ // N : 듣도 못한 사람의 수, M : 보도 못한 사람의 수	
	cin >> str
    map[str] ++
}

for(auto i : map.begin ~ map.end){
	if(i->second >= 2){
    	cnt ++
        vector.push_back(i->first)
    }
}

print(cnt, vector)

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

N, M의 범위가 500,000 이하이므로 알고리즘을 잘 짜면 일반 벡터로도 풀 수 있을 것 같긴하다.
하지만 map을 사용하면 훨씬 편하게 풀 수 있는 문제였다.