[알고리즘] 코드잇 - 중복되는 항목 찾기1(Python)

실습설명

(N+1)의 크기인 리스트에, 1부터 N까지의 임의의 자연수가 요소로 할당되어 있습니다. 그렇다면 어떤 수는 꼭 한 번은 반복되겠지요.

 

예를 들어 [1,3,4,2,5,4]와 같은 리스트가 있을수도 있고, [1,1,1,6,2,2,3]과 같은 리스트가 있을 수도 있습니다.(몇 개의 수가 여러 번 중복되어 있을 수도 있습니다.)

 

이런 리스트에서 반복되는 요소를 찾아내려고 합니다.

 

중복되는 어떠한 수 '하나'만 찾아내도 됩니다. 즉 [1,1,1,6,2,2,3]예시에서 1,2를 모두 리턴하지 않고, 1또는 2 하나만 리턴하게 하면 됩니다.

 

중복되는 수를 찾는 시간 효율적인 함수를 설계해 보세요.

 

힌트1

Brute Force 접근법을 이용해서 리스트 내에 있는 모든 조합을 다 확인하면 쉽게 답을 구할 수 있습니다.

 

이중 중첩 반복문으로 리스트를 돌면서 각 요소마다 리스트 내에 있는 나머지 요소들과 비교해보며, 중복되는 요소를 리턴하는 거죠.

def find_same_number(some_list):
    # 가능한 모든 조합을 다 돌면서 반복 요소가 있는지 확인하고 있으면 해당 요소를 리턴한다
    for i in range(len(some_list)):
        for j in range(i + 1, len(some_list)):
            if some_list[i] == some_list[j]:
                return some_list[i]

print(find_same_number([1, 1, 1, 6, 2, 2, 3]))

이렇게 하면 인풋 리스트의 길이가 n이라고 할 떄, 인풋 리스트 길이에 비례하는 이중 중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n^2)이 되겠네요. 쉽게 생각해 낼 수 있고 무조건 답을 구할 수 있습니다.

 

하지만 문제의 조건이 시간 효율적인 함수를 작성하는 것이었는데요. O(n^2)은 그다지 효율적인 방법 같지는 않군요.

 

모든 조합을 다 확인해 보는것보다 효율적인 방법을 생각해 봅시다.

 

힌트2

반복문으로 리스트를 돌면서 요소를 하나씩 볼때, 해당 요소를 이미 보았는지 어떻게 확인 할 수 있을까요? 한번 본 요소들을 어딘가에 저장하면 다음에 다시 보게 되면 알 수 있습니다. 

 

이미 나온 여러개의 요소를 저장할 수 있는 방법이 무엇이 있을지 생각해 보세요.

 

힌트3

여러개의 요소를 저장할 수 있는 도구는 리스트와 사전이 있는데요. 둘 중 어떤 것을 쓰는지 크게 중요하지는 않지만 사전을 사용해 볼게요. 아래 리스트에 반복되는 요소가 있는지 확인하고 싶다고 생각해 봅시다. 중봅되는 요소를 담을 사전 elements_seen_so_far = []가 있다고 가정하겠습니다.

 

[1,2,4,2,5,3]

1. 0 번째 요소 1이 사전에 있는 key인지 확인합니다(이미 본 요소인지 확인합니다.)  

   처음 보는 요소이기 떄문에 사전에 추가해 줍니다.

   (elements_seen_so_far[1] = True)

2. 1번째 요소 2도 마찬가지로 사전에 추가합니다.

3. 2번째 요소 4도 마찬가지로 사전에 추가합니다.

4. 3번째 요소 2는 elements_seen_so_far에 이미 있는 key기 때문에 2를 리턴합니다.

 

시간복잡도는 가능한 요소의 조합들을 다보는 O(n^2)보다 효율적인 O(n)로 풀수 있습니다.

 

답안

def find_same_number(some_list):
    # 이미 나온 요소를 저장시켜줄 사전
    elements_seen_so_far = {}

    for element in some_list:
        # 이미 나온 요소인지 확인하고 맞으면 요소를 리턴한다
        if element in elements_seen_so_far:
            return element

        # 해당 요소를 사전에 저장시킨다
        elements_seen_so_far[element] = True

print(find_same_number([1, 4, 3, 5, 3, 2]))
print(find_same_number([4, 1, 5, 2, 3, 5]))
print(find_same_number([5, 2, 3, 4, 1, 6, 7, 8, 9, 3]))