중복되는 값 찾기

방법 1: set 사용

• 첫 번째 원소와 그 다음 원소부터 마지막 원소까지 값을 비교한다.
• 만약 값이 동일할 경우 set 목록에 해당 원소를 추가한다.
• 두 번째 원소부터 마지막 원소까지 앞의 과정을 반복한다.
• 마지막 원소는 그 다음 원소가 없기 때문에 굳이 비교하지 않아도 된다.

시간 복잡도

• ${O(N^2)}$

def find_duplicates(data):
    """
    중복되는 원소를 찾아 반환합니다.
    시간 복잡도: O(N^2) (효율적인 방법은 아님)
    """
    n = len(data)
    duplicates = set()
    for i in range(n - 1):
        for j in range(i + 1, n):
            if data[i] == data[j]:
                duplicates.add(data[i])

    return duplicates


if __name__ == '__main__':
    numbers = [1, 1, 2, 3, 3]
    fruits = ['Apple', 'Peach', 'Banana', 'Peach', 'Apple']

    same_numbers = find_duplicates(numbers)
    same_fruits = find_duplicates(fruits)

    print(same_numbers)
    print(same_fruits)

'''
출력 결과

{1, 3}
{'Apple', 'Peach'}
'''

방법 2: dictionary 사용

• 주어진 리스트를 돌면서 원소가 딕셔너리의 키 값으로 있는지 확인한다.
• 있을 경우, 키의 값을 1 증가시킨다.
• 없을 경우, 키에 값을 1 저장한다.
• 딕셔너리 키를 돌면서 값이 2 이상인 것을 찾는다.

시간 복잡도

• ${O(N)}$
• 방법 1에 비해 시간 복잡도가 줄었지만, 원소의 키와 값을 각각 저장해야 하므로 더 많은 저장 공간을 사용한다. (공간 복잡도를 희생하여 시간 복잡도를 개선)

def find_duplicates(data):
    """
    중복되는 원소를 찾아 반환합니다.
    시간 복잡도: O(N)
    """
    n = len(data)
    count_dict = dict()

    for i in range(n):
        now = data[i]
        count_dict[now] = count_dict.get(now, 0) + 1

    duplicates = set()
    for key, value in count_dict.items():
        if value > 1:
            duplicates.add(key)

    return duplicates


if __name__ == '__main__':
    numbers = [1, 1, 2, 3, 3]
    fruits = ['Apple', 'Peach', 'Banana', 'Peach', 'Apple']

    same_numbers = find_duplicates(numbers)
    same_fruits = find_duplicates(fruits)

    print(same_numbers)
    print(same_fruits)

'''
출력 결과

{1, 3}
{'Apple', 'Peach'}
'''