[BOJ] #10815 숫자카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

---

저번 글이었던 7785번과 상당히 유사한 문제다. set을 이용하는 문제이며, set 컨테이너를 이용해야겠다고 마음먹고는 거진 10분만에 풀어버렸다. 문제 난이도 또한 상당히 쉽다. 하지만, 최댓값이 500,000이기에 O(N^2)인 경우 시간초과가 나지않을까 잠깐 걱정했으나, set컨테이너에서 특정 값을 찾는 find 메소드의 시간복잡도는 O(logN)에 불과하기 때문에, 반복문 안에 넣어도 O(NlogN)정도밖에 안나온다. 이 문제의 시간제한이 2초나 되기때문에, 그럴 염려는 없다고 판단한 후 바로 풀어냈다.

#include <iostream>
#include <set>

using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    set<int> s;
    for (int i=0; i<N; i++) {
        int a;
        cin >> a;
        s.insert(a);
    }

    int M;
    cin >> M;

    set<int>::iterator it;
    for (int i=0; i<M; i++) {
        int a;
        cin >> a;

        it = s.find(a);
        if (it != s.end()) cout << 1 << ' ';
        else cout << 0 << ' ';
    }
    printf("\n");

    return 0;
}

---

set 컨테이너에서 특정한 값이 있는지 없는지 판별하기

set<int>::iterator it; //iter 선언

it = s.find(a);
if (it != s.end()) cout << 1 << ' '; //값이 존재함
else cout << 0 << ' '; //값이 존재하지않음

ㅇset을 순회할 수 있는 iterator를 선언해준 다음, find() 메소드를 이용해 찾으면 된다. 만약 특정 값이 존재한다면 해당 인덱스의 iter값을 반환하고, 존재하지 않는다면 end() 포인터를 반환한다. 이를 이용해 간단히 조건문으로 구현 가능하다.
* find() 메소드의 시간복잡도는 O(logN)에 해당한다. 상당히 빠르게 원하는 값을 찾을 수 있다.