같은 데이터 빠르게 찾기 JAVA / C++ / 파이썬

Hash Map 자료구조는 key를 해싱하여 저장하고 빠르게 탐색합니다.
시간복잡도는 O(1)입니다.

자료구조에 대해 직관적인 이해를 하기 위해 적절한 알고리즘 문제를 찾았습니다.
백준 14425 문자열 집합 문체를 풀면서 Hash Map 또는 Set 자료구조에 대해 생각해 봅시다.

 

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

14425번: 문자열 집합

예제를 보면 5개의 문자열이 나옵니다. 이를 집합 S라 합니다.

그리고 11개의 문자열이 나오는데 이 11개 중 몇개가 집합 S에 속하는지 찾는 문제입니다.

 

N의 개수는 최대 10,000

M의 개수는 최대 10,000

 

단순히 생각하면 M을 N만큼 반복해서 일치하는지 개수를 세면 문제가 풀립니다.

시간 복잡도는 O(M*N) = 10,000 * 10,000 = 100,000,000 = 1초

시간초과가 발생합니다.

 

따라서 해싱을 제공하는 자료구조를 활용해서 O(M) = 10,000 = 0.0001초만에 답을 찾아야 합니다.

 

1. JAVA

HashMap 선언하고 S집합에 속할 문자열을 넣습니다.

그리고 검사할 M개의 문자열(키)가 있는지 체크하여 답을 찾습니다.

같은 데이터를 가장 빠르게 찾는 방법입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {   
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    
	    int N = Integer.parseInt(st.nextToken());
	    int M = Integer.parseInt(st.nextToken());
	    
	    HashMap<String, Integer> a = new HashMap<String, Integer>();
	    
	    for(int i = 0; i < N; i++){
			a.put(br.readLine(), 1);
		}
	    
	    int ans = 0;
	    for(int i = 0; i < M; i++){
			if(a.containsKey(br.readLine())) {
				ans++;
			}
		}
	    System.out.println(ans);
	}
}

 

2. C++

map 자료형은 키, 벨류를 사용합니다.

그런데 이 문제에서 벨류는 전혀 필요가 없습니다.

메모리가 아깝기 때문에 키만 가지고 있는 set 자료구조를 활용하겠습니다.

#include <iostream>
#include <set>

using namespace std;

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

	int N, M;
	cin >> N >> M;

    set<string> a;

	for (int i = 0; i < N; i++) {
		string temp;
		cin >> temp;
		a.insert(temp);
	}
	
	int ans = 0;
	for (int i = 0; i < M; i++) {
		string temp;
		cin >> temp;
		if (a.find(temp) != a.end()) {
			ans++;
		}
	}

	cout << ans;
	return 0;
}

 

3. 파이썬

python 에서는 set() 집합을 선언하고 그곳에 문자열을 add 합니다.

in 키워드로 집합에 동일한 문자열이 있는지 찾아냅니다.

아주 간단한 소스입니다.

N, M = map(int, input().split())
a = set()

for i in range(N):
    a.add(input())

ans = 0
for i in range(M):
    temp = input()
    if temp in a:
        ans += 1

print(ans)

각 언어별로 중복되지 않은 데이터 중에 같은 데이터를 가장 빨리 찾는 방법을 배웠습니다.

중복이 없고 삽입하고 찾는데 O(1) 시간복잡도를 갖는 자료구조 map 또는 set을 사용하는게 핵심입니다.