백준 #1920 수찾기

백준 #1920 수찾기

이 문제를 vector로 사용해서 풀었을 때는 시간초과가 났어서 ( M의 범위가 100,000까지이기 때문) 다음에 다시 풀기로 했었다.

unordered_set(해시 테이블을 사용한 집합 자료구조)을 사용하면 시간 복잡도 O(1)로 삽입과 검색을 사용할 수 있기에 이를 이용하였다.

풀이

#include <iostream>
#include <unordered_set>

#define MAX 100001

using namespace std;

int main(){
ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >>N;
    unordered_set<int> map;
	
     for(int i = 0 ; i < N ; i++){
      int num ;
      cin >> num;
      map.insert(num);
      
    }
    
    cin >>M;
    for(int i = 0 ; i < M ; i++){
    	int num;
    	cin >> num ;
    	if(map.find(num) != map.end()) cout<< 0 << '\n';
        else cout<< 0 << '\n';
    }
    return 0;
}

추가 내용)

unordered_set은 해시 테이블을 사용한 집합 자료구조로,단일 값만 저장하며 중복을 허용하지 않으며 순서를 보장하지 않는다.

unordered_map은 해시 테이블을 사용한 맵 자료구조로, 키-값 쌍을 저장하고, 중복된 키는 허용하지 않으며, 평균적으로 매우 빠른 탐색 속도를 제공한다.

공통적으로 이 두 자료구조는 O(1)의 평균 시간 복잡도로 삽입,삭제,검색을 수행할 수 있기 때문에 효율적이다.

입력받은 숫자의 갯수도 저장하려면 unordred_map을 선택하고, 입력받은 숫자의 여부만 필요하다면 unorder_set을 사용하는 게 맞겠다.