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

* <모두의 알고리즘 with 파이썬>의 문제 03를 정리한 내용입니다.

 

1. 동명이인 찾기 알고리즘

• 설명: 집합(set)을 사용하여 중복된 값을 찾는 문제이다. 입력으로는 n명의 이름이 있는 리스트가 들어가고, 이 중 중복되는 이름을 제외하고 unique 이름만 집합으로 반환해야한다.
• 주의 해야하는 포인트: 
  • 비교할 이름을 뽑은 다음에는 순서상 뒤에 이름들 하고만 비교하면 된다. 순서상 앞에 있는 이름들 하고는 비교할 필요가 없다. 
  • 리스트의 마지막 이름을 기준으로는 비교하지 않아도 된다. 마지막보다 한 번째 앞의 이름과 이미 비교가 끝났다. 
  • 같은 이름을 찾으면 결과(result) 집합에 해당 이름을 추가한다. 
• 사용하는 함수:

함수	설명
len(s)	집합의 길이를 구함
add(x)	집합에 x라는 자료를 추가함
discard(x)	집합에 자료 x가 들어있다면 삭제함
clear	집합의 모든 자료를 지움
x in s	어떤 자료 x가 집합 s에 들어있는지 확인함
update(x)	집합에 여러 개의 값을 한꺼번에 추가함
remove(x)	집합에 자료 x가 들어있다면 제거함

 

 

2. 집합 (set)

• 이 문제에서 사용하는 집합 자료형은 크게 두 가지 특징이 있다. 첫 번째, 중복을 허용하지 않는다. 두 번째, 순서가 없다. 중복을 허용하지 않는다는 점에서 딕셔너리와 유사한 면이 있다. 이러한 특징 때문에 중복을 제거하기 위한 필터 역할로 종종 사용하는 자료형이다. 
• 하지만 순서가 없기 때문에, set 자료형에 저장된 값을 인덱싱으로 접근하려면 튜플이나 리스트로 변환 후 사용해야한다. 

 

 

3. 알고리즘 풀이 

3.1 동명이인을 찾는 알고리즘 

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', 'Jerry', 'Mike', 'Tom']
print(find_same_name(name))

 

3.2 두 명을 뽑아 짝을 짓는 알고리즘 

• n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘 

def pair_name(a):
    n = len(a)
    result = set()
    
    for i in range(0, n-1):
        for j in range(i+1, n):
            result.add((a[i], a[j]))
            
    return result 


name = ['Tom', 'Jerry', 'Mike', 'Tom']
print(pair_name(name))