집합을 이용한 중복 제거 알고리즘 (with Python3)

중복을 제거할때는 set 집합을 이용한다.

 

집합의 특징

• 중복이 없다. (집합 내의 원소들은 서로 다른 원소를 가진다)
• 순서가 없다. (원소간의 순서를 가지지 않는다)

 

중복된 원소를 제거할때, 집합(set)을 이용하면 효율적이다.

 

예제. 동명이인 찾기

n 명의 주어진 이름들이 있을때, 동명이인인 이름을 찾는다.

 

• 예제 입력: Tom Mike Jerry Tom
• 예제 출력: Tom

 

코드

2가지 방법으로 풀어볼 수 있다.

1. test1() 메소드와 같이 집합을 이용하는 방법.
2. test2() 메소드와 같이 하나 하나 모두다 비교해서 답을 찾는 방법.

# -*- coding: utf-8 -*-

import unittest


class Exam03(unittest.TestCase):
    """n 명의 주어진 이름들이 있을때, 동명이인인 이름을 찾는다."""

    @classmethod
    def setUp(cls):
        cls.names = ["Tom", "Jerry", "Mike", "Tom"]

    def test1(self):
        """방법 1. 집합을 이용한 방법"""
        name_set = set()
        duplicated_names = set()
        for name in self.names:
            if name in name_set:
                duplicated_names.add(name)
            name_set.add(name)
        self.assertEqual({"Tom"}, duplicated_names)

    def test2(self):
        """방법 2. 단순 비교해봄"""
        name_len = len(self.names)
        duplicated_names = list()
        for idx, name in enumerate(self.names):
            for i in range(idx + 1, name_len):
                if name == self.names[i]:
                    duplicated_names.append(name)
        self.assertEqual(["Tom"], duplicated_names)


if __name__ == "__main__":
    unittest.main()

 

시간 복잡도

1. test1(): O(N)
2. test2(): O(N-1 + N-2 + ... + 2 + 1) = O(N * (N-1)/2) = O(N^2)

시간 복잡도를 통해 집합을 이용하여 문제를 푸는것이 더 효율적(시간 복잡도 관점에서 봤을때)이다.

Reference

• https://thebook.io/006935/part01/ch03/02/