백준 | 1920. 수 찾기

10/08

그니까 문제가

4 1 5 2 3 여기 안에 1 3 7 9 5 얘네가 들어가있으면 1, 아님 0을 출력하는거

1 있음 => 1

3 있음 => 1

7 없음 => 0

9 없음 => 0

5 있음 => 1

이렇게

#include <iostream>
#include <map>
using namespace std;

int main(){
    int N, M, x;
    cin >> N;
    map<int, int>m;
    while(N--){
        cin >> x;
        m[x]++;
    }
    cin >> M;
    while(M--){
        cin >> x;
        int ans = m[x] > 0 ? 1 : 0;
        cout << ans << "\n";
    }
}

 

그래서 map으로 있는지 없는지 count 해서 하게 했는데

시간초과가 나와서

다른 방법을 써야한다.

 

map 말고 자동으로 체이닝 해주는 unordered set 써보기로!

 

#include <iostream>
#include <unordered_set>
using namespace std;

int main(){
    int N, M, x;
    cin >> N;
    unordered_set<int>us;
    while(N--){
        cin >> x;
        us.insert(x);
    }
    cin >> M;
    while(M--){
        cin >> x;
        int ans = us.find(x) == us.end()? 0 : 1;
        cout << ans << "\n";
    }
}

 

unordered_set 써봤는데 이것도 시간초과 나온다

 

10/31

  입출력을 cin, cout 써서 그런거같아서 바꿔줬더니 맞았다

 

#include <cstdio>
#include <unordered_set>

using namespace std;

int main(){
    int N, M, x;
    scanf("%d", &N);
    unordered_set<int>us;
    while(N--){
        scanf("%d", &x);
        us.insert(x);
    }
    scanf("%d", &M);
    while(M--){
        scanf("%d", &x);
        int ans = us.find(x) == us.end()? 0 : 1;
        printf("%d\n", ans);
    }
}

  

짜잔~

 

조금 더 공부해보니까 unordered_set 말고

sort + binary_search을 활용해서 푸는 방법도 있다고 해서 찾아봤다

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N, M, x;
    scanf("%d", &N);
    vector <int> v (N);
    for(int i = 0; i<N; i++) scanf("%d", &v[i]);
    sort(v.begin(), v.end());
    scanf("%d", &M);
    
    while(M--){
        scanf("%d", &x);
        int ans = binary_search(v.begin(), v.end(), x);
        printf("%d\n", ans);
    }
}

 

이렇게!

위에가 unordered_set으로 푼 거

아래가 sort + binary_search로 푼거

메모리랑 시간 차이가 꽤 나서 왜그런지 궁금해짐

 

	unordered_set	sort + binary_search
코드	unordered_set us; us.insert(x); us.find(x);	vector v; sort(v.begin(), v.end()); binary_search(v.begin(), v.end(), x);
삽입	평균 O(1)	O(N log N) (정렬 포함)
탐색	평균 O(1), 최악 O(N)	O(log N)
메모리 사용량	높음(해시 버킷)	낮음
정렬	필요없음 XX	필요함 OO
입츌력 속도	큼 (입출력 느리면 시간초과 위험)	작음
성능 안정성	데이터 분포 따라 다름	매우 안정적
용도	중복제거, 실시간 삽입 위주	검색/ 조회 위주

 

둘이 용도가 달라서 쓰임이 다른 듯

한 번에 데이터 입력 후, 여러 번 찾기만 함	✅ binary_search (정렬 후 탐색)
데이터가 계속 추가/삭제됨	✅ unordered_set
메모리 제약이 있음	binary_search
입력이 많고 불규칙함	binary_search (충돌 영향 없음)
빠른 중복 체크가 필요함	unordered_set