[unordered_set & find] codility 사전 테스트 문제 풀이

사전테스트 URL: https://app.codility.com/demo/take-sample-test/

이전 코드 (O(N^2))

int solution(vector<int> &A) {
    sort(A.begin(), A.end());

    int i = 1;
    while(i < 100001) {
        int flag = 0;
        for(int j=0;j<A.size();j++) {
            if (i == A[j]) {
                flag = 1;
                i++;
                break;
            }
        }
        if (flag == 0) {
            break;
        }
    }
    return i;
}

• 1부터 100001까지 진행하면서 vector A에 포함되어 있지 않은 수를 찾으려 함
• Time complexity = O(N * M), 자칫하면 Time Out의 위험이 있음 ⇒ 25%의 성능이 나옴

온전한 풀이 (O(N logN))

int solution(vector<int> &A) {
    sort(A.begin(), A.end());

    int smallestPositive = 1;

    for (int i = 0; i < A.size(); i++) {
        if (A[i] == smallestPositive) {
            smallestPositive++;
        }
    }

    return smallestPositive;
}

• smallestPositive를 1부터 올려가면서 정렬된 vector A의 요소와 같을 때만 smallestPositive의 값을 올린다.
• 다를 경우 smallestPositive의 값은 올라가지 않기 때문에 for문이 끝나면 그대로 값이 유지된다.
• Time complexity = O(M)

최적의 풀이 (O(N))

int solution(vector<int> &A) {
  unordered_set<int> elements;
  
  for (int num : A) {
      if (num > 0) {
          elements.insert(num);
      }
  }
  
  int smallestPositive = 1;
  while (elements.find(smallestPositive) != elements.end()) {
      smallestPositive++;
  }
  
  return smallestPositive;
}

두가지 다른점

sort(A.begin(), A.end());

unordered_set<int> elements;

• sort를 사용할 경우 time complexity는 $O(NlogN)$

• unordered_set은 정렬하지 않지만 중복을 없애준다.

    int solution(vector<int> &A) {
      int smallestPositive = 1;
      while (find(A.begin(), A.end(), smallestPositive) != A.end()) {
          smallestPositive++;
      }
        
      return smallestPositive;
    }
  

  • unordered_set을 사용하지 않게 될 경우 성능이 25% 떨어지게 된다.
  • vector의 find함수는 vector의 begin부터 end까지 선형 탐색을 수행
  • 시간 복잡도는 O(N)
  • while 반복문의 횟수가 최대 N번까지 갈 수 있으므로 전체 시간 복잡도는 $O(N^2)$가 됩니다.

vector의 find함수와 unordered_set의 find함수

unordered_set은 해시 테이블(Hash Table) 기반의 자료구조로, 원소를 저장하고 탐색할 때 해시 값을 이용합니다. unordered_set의 find 함수는 특정 원소가 집합에 있는지 확인하고, 그 위치를 반환합니다.

• 시간 복잡도: 평균적으로 O(1), 최악의 경우 O(N) (해시 충돌이 많이 발생하는 경우)

std::find는 선형 탐색(Linear Search)을 수행하므로, 특정 원소가 있는지 확인하기 위해 처음부터 끝까지 순회해야 합니다.

• 시간 복잡도: O(N)

set과 unordered_set

정렬도 되지 않는 unordered_set을 쓰는 이유는 실행 시간 차이 때문이다. unordered_set은 insert, erase, find 모두가 O(1) 으로 수행된다!

set의 경우 O(logn) 이었지만 unordered_set의 경우 상수 시간에 원소를 삽입하고, 검색할 수 있다.

수행시간이 다른 이유는 set은 레드블랙트리, unordered_set은 해시테이블로 구현되었기 때문이다. 따라서 딱히 정렬을 하지 않아도 될 상황에서는 unordered_set을 사용하는 것이 더 좋다고 할 수 있다.

출처 : https://velog.io/@mingyo0125/C-set%EA%B3%BC-unorderdset