[알고리즘] 동명이인 찾기

Q. n명 사람 이름 중에서 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 만들어 보세요

names = ["Tom","Mike","Jerry","Tom"]
return {"Tom"}

1. 첫번째 Tom을 뒤에 있는 Mike,Jerry,Tom과 차례로 비교합니다.
2. 첫번째 Tom과 마지막 Tom이 같으므로 동명이인 입니다.(동명이인:Tom)
3. 두번째 Mike를 뒤에 있는 Jerry,Tom과 비교합니다.(앞에있는 Tom은이미 비교함)
4. 세번째 Jerry를 뒤에있는 Tom과 비교합니다.
5. 마지막 Tom은 앞에서 이미 비교했기 때문에 비교하지 않아도 됩니다.

def find_same_name(a):
	n = len(a)
    result = set()
    for i in range(0,n-1):
    	for j in range(i+1,n):
        	if a[i] == a[j]:
            	result.add(a[i])
    return result
   
name = ["Tom","Mike","Jerry","Tom"]
print(find_same_name(name))

{'Tom'}

계산 복잡도

같은 이름을 찾는 알고리즘으로 두 이름이 같은지 비교하는 횟수를 따져보면 됩니다.

입력 크기 n일 경우,
전체 비교 횟수는 0 + 1 + 2 + ... + (n-1)번, 즉 1부터 (n-1)까지의 합

1/2n^2 - 1/2n번 비교를 해야합니다.

대문자 O 표기법으로 O(n^2)이라고 표현합니다.