중복 확인 알고리즘 - jungbog hwag-in algolijeum

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

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

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

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

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]))

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

하지만 문제의 조건이 시간 효율적인 함수를 작성하는 것이었는데요, O(n^2)O(n2)은 그다지 효율적인 방법 같지는 않군요. 모든 조합을 다 확인해보는 것보다 효율적인 방법을 생각해봅시다.

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

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

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

리스트는 중복해서 값을 가지고 있을 수 있지만 딕셔너리는 중복된 키를 가질 수 없기 때문에 쉽게 특정 값을 키로 사용해서 이미 사용했다는 표기만 하기 위해 value에 True를 사용합니다. 그리고 중복된 값을 걸러내려고 하는데 리스트에서는 값이 있는지 없는지 확인하기 위해 전체를 탐색해야 합니다. 하지만 딕셔너리는 내부적으로 해시테이블이라 키만 넣으면 값이 나오는 구조이기도 합니다.

중복되는 요소를 담을 사전 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(n2)보다 효율적인 O(n)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]))

출력

3
5
3

효율적이게 이미 나온 요소들을 저장하고 반복되는 요소를 저장할 수 있습니다!

공간 복잡도
인풋 리스트의 길이가 nn이라고 할 때 사전의 크기는 인풋에 비례하는 크기를 갖겠죠?

이 알고리즘의 공간 복잡도는 O(n)O(n)이 됩니다.

def find_same_number(some_list):
    #시간복잡도 O(n)
    check_list = [0 for _ in range(len(some_list))]
    #시간복잡도 O(n)
    for i in range(len(some_list)):
        check_list[some_list[i]] += 1
        if check_list[some_list[i]] >= 2:
            return some_list[i]

# 중복되는 수 ‘하나’만 리턴합니다.
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]))

안녕하세요,

L이 리스트인 경우 if e in L:의 시간복잡도는 O(n)입니다 (선형탐색을 해야합니다).

L이 사전인 경우 if e in L:의 시간복잡도는 O(1)입니다. 간단히 설명을 드리자면 hash함수 h:Keys-> Indices 는 키를 사전 인덱스로 mapping하기 때문에 (mapping과정은 O(1)입니다) 사전에서 어디를 찾아봐야 하는지 바로 알 수 있습니다.

배열 안의 element가 중복되는 값을 가지는지 체크하는

3가지 방법을 소개합니다.

1. 반복문 이용하기
2. Set 객체 이용하기
3. some(), indexOf(), lastIndexOf() 함수 이용하기

1. 반복문 이용하기

const arr = ['a', 'b', 'c', 'b'];

let dupYn = false;
for(let i = 0; i < arr.length; i++) {
  const currElem = arr[i];
  
  for(let j = i+1; j < arr.length; j++) {
    if(currElem === arr[j]) {
      dupYn = true;
      break;
    }
  }
  
  if(dupYn)  {
    break;
  }
}

document.writeln("DupYn : " + dupYn);

가장 기본적인 방법인 반복문을 이용하여 중복을 체크하는 코드입니다.

위 코드는 2개의 반복문을 사용하였습니다.

첫번째 반복문에서는 배열의 원소들을 순차적으로 순회하고,

두번째 반복문에서는 첫번째 반복문에서 선택된 원소 이후의 값을 순차적으로 순회합니다.

그리고, 첫번째 반복문에서 선택된 원소와 두번째 반복문에서 선택된 원소의 값을 비교하여

동일한 값이 있을 경우 dupYn을 true로 설정하고 반복문을 중단합니다.

이 코드에서는 arr[0]의 값과 arr[3]의 값이 동일하므로, dupYn 값은 true를 리턴합니다.

2. Set 객체 이용하기

Set은 중복을 허용하지 않는 값을 모아놓은 Collection 객체입니다.

new Set([iterable]);

Set 객체는 new 연산자를 사용하여 생성하고, 파라미터로 iterable 객체를 전달합니다.

배열은 iterable 객체이므로, 배열을 파라미터로 전달하여 Set 객체를 생성할 수 있습니다.

const arr = ['a', 'b', 'c', 'b'];
const set = new Set(arr);

document.writeln(arr.length); // 4
document.writeln(set.size); // 3

// duplicate
if(arr.length !== set.size) {
  document.writeln("duplicate");
}

const arr = ['a', 'b', 'c', 'b'];

arr.length; // 4

배열 arr의 길이는 4입니다.

const set = new Set(arr);

set.size; // 3

배열 arr를 new Set의 파라미터로 전달하여 set 객체를 생성하였습니다.

Set은 중복되는 값을 허용하지 않으므로, 

set 객체는 중복된 값을 제거한 'a', 'b', 'c' 값만 가지게 됩니다.

따라서, set 객체의 크기는 3입니다.

if(arr.length !== set.size)  {

   document.writeln("duplicate");

}

Set은 중복을 허용하지 않는 다는 점을 활용하여,

원본 배열의 크기와, 원본 배열을 가지고 생성한 Set 객체의 크기를 비교하여

중복이 존재하는지 확인 할 수 있습니다.

3. some(), indexOf(), lastIndexOf() 함수 이용하기

 some() 함수 

arr.some(callback(element[, index[, array]])[, thisArg])

 some() 함수는 

배열에서 값을 찾는 조건을 callback 함수로 전달하고,

배열에 조건에 맞는 값이 하나라도 있는지 여부(boolean)를 리턴하는 하는 함수입니다.

조건에 맞는 값이 있으면 true, 조건에 맞는 값이 없으면 false를 리턴합니다.

[Javascript] 배열에 특정 값이 포함되어 있는지 여부 체크하기

 indexOf(), lastIndexOf() 

arr.indexOf(searchElement[, fromIndex])
arr.lastIndexOf(searchElement[, fromIndex])

 indexOf() 함수는 

배열 안에서 찾으려는 값(searchElement)과 정확하게 일치(===)하는'첫번째' element의 index를 리턴합니다. 

 lastIndexOf() 함수는 

배열 안에서 찾으려는 값(searchElement)과 정확하게 일치(===)하는 '마지막' element의 index 를 리턴합니다.

[Javascript] 배열에 특정 값이 포함되어 있는지 여부 체크하기

이 세 가지 함수 ( some(), indexOf(), lastIndexOf() ) 를 사용하여

배열 원소의 중복 여부를 체크할 수 있습니다.

function isDuplicate(arr)  {
  const isDup = arr.some(function(x) {
    return arr.indexOf(x) !== arr.lastIndexOf(x);
  });
                         
  return isDup;
}

const result = isDuplicate(['a', 'b', 'c', 'b']);
// true
document.writeln(result);

배열을 파라미터로 받아서, 

배열 원소의 중복을 체크하는 함수인 isDuplicate()를 정의하였습니다.

arr.some(function(x) {

   return arr.indexOf(x) !== arr.lastIndexOf(x);

});

arr.some() 함수는 배열(arr)의 원소를 순서대로 callback 함수로 전달하고, callback 함수를 실행합니다.

arr.indexOf(x)는 원소 x가 있는 첫번째 index를 리턴합니다.

arr.lastIndexOf(x)는 원소 x가 있는 마지막 index를 리턴합니다.

만약, 배열 안에 원소 x가 유일하다면(중복이 존재하지 않는다면), 두 index값은 같을 것입니다.

만약, 배열 안에 원소 x가 중복된다면, 두 index 값은 다를 것입니다.

그래서 arr.some()으로 전달된 callback 함수는 

중복이 존재하면 true를 리턴하고, 중복이 존재하지 않으면 false를 리턴합니다.

some() 함수는 callback 함수가 한 번이라도 true를 리턴하면, true를 리턴합니다.

배열 원소의 중복 여부를 체크하는 방법을 알아보았습니다.