3 동명이인 찾기

입력은 n 명의 이름이 들어있는 리스트

결과는 이름들이 들어있는 집합

집합은 중복 제거 가능

#  중복 이름 찾기 
# 1. 비교 
def find_same_name(array) :
    original=[]
    duplicate=[]
    for i in array:
        if i not in original: # 처음 
            original.append(i)
        else : # 중복 될 경우 
            if i not in duplicate: #duplicate 배열에 없으면 넣기 
                duplicate.append(i)
    return duplicate

print(find_same_name(["tom","jerry","mike","tom"]))

def find_same_name2(array):
    num=len(array)
    result = set()
    for i in range(0,num-1): # 0부터 num-2 까지 반복 
        for j in range(i+1,num):  # i+1부터 n-1까지 반복 
            if(array[i]==array[j]):
                result.add(array[i])
    return result            

print(find_same_name2(["tom","jerry","mike","tom"]))

시간복잡도 O(N제곱)

연습문제

# 두명을 뽑아 짝을 짓는다. 모든 조합을 출력하는 알고리즘 
# 앞에랑 뒤에만 뽑아서 출력 
def make_partner(array) :
    length=len(array)
    for i in range(0,length):
        for j in  range(i+1,length):
            print(array[i] + ' - ' +array[j])

make_partner(['Tom','Jerry','Mike'])

시간복잡도

65536 = O(1)

n-1 = O(n)

2N(2)/3 +10000n = O(n2)