[백준] 1920 수찾기 c++

 

문제 링크 https://www.acmicpc.net/problem/1920

KEY

이중for문을 돌려서 일일이 확인하는 작업은 100,000 * 100,000 O(N^2)으로 시간초과가 발생한다.

따라서 O(logN)의 시간복잡도를 갖는 이분탐색과 map, ordered_map을 활용하여 풀이할 수 있다.

• unordered_map: HashTable로 구현된 자료구조. 탐색 시 O(1)의 시간복잡도
• map: 이진탐색트리로 구현된 자료구조. 탐색 시 O(logN)의 시간복잡도.

map의 경우 자동으로 정렬되므로(Red Black Tree의 특징) 삽입/삭제가 빈번할 경우 성능이 저하되는 특징이 있다. 따라서 이 문제와 같은 경우 최대 100,000번 불필요한 정렬을 할 수 있으므로, unordered_map을 사용하여 풀이했다.

unordered_map 풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
using namespace std;
int N, M;
unordered_map<int, int> m;
vector<int> answer;
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) { //(숫자, 갯수)형태의 (key, value)를 unordered_map에 저장
        int num;
        cin >> num;
        m[num]++;
    }
 
    cin >> M;
    for (int i = 0; i < M; i++) {
        int value;
        cin >> value;
 
        if (m[value]) { //값이 존재하면 1
            answer.push_back(1);
        }
        else { //값이 존재하지 않으면 0
            answer.push_back(0);
        }
    }
    for (auto i : answer)
        cout << i << "\n";
}

 

이분탐색 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
vector<int> A;
vector<int> answer;
 
bool BS(int value) { //이분탐색
    int start = 0;
    int end = N - 1;
 
    while (start <= end) {
        int mid = (start + end) / 2;
        if (A[mid] > value) {
            end = mid - 1;
        }
        else if (A[mid] < value) {
            start = mid + 1;
        }
        else {
            return true;
        }
    }
    return false;
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        A.push_back(num);
    }
 
    sort(A.begin(), A.end());
 
    cin >> M;
    for (int i = 0; i < M; i++) {
        int value;
        cin >> value;
 
        if (BS(value)) { //값이 있다면
            answer.push_back(1);
        }
        else { //값이 없다면
            answer.push_back(0);
        }
    }
 
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << "\n";
    }
 
}