[백준/Baekjoon] 2776 암기왕 C++ :: Binary Search & map

 

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

2776번: 암기왕

---

1. Logic

이 문제는 unordered_map을 활용한 풀이, 이분탐색을 활용한 풀이 총 두가지 방법으로 풀이 가능하다.

---

2. Code

해시 맵 풀이

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; 
    cin >> t;
    
    while(t--) {
        int n, m;
        unordered_map<int, bool> Map;
        
        cin >> n;
        for(int i = 0; i < n; i++) {
            int a;
            cin >> a;
            Map[a] = true;
        }
        
        cin >> m;
        for(int i = 0; i < m; i++) {
            int a;
            cin >> a;
            
            if(Map[a]) {
                cout << "1\n";
            }
            else cout << "0\n";
        }
    }    
}

이분탐색 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long n, m;
vector<long long> note1;

long long binarySerach(long long goal) {
    long long left = 0;
    long long right = n-1;
    long long mid;
    
    while(left <= right) {
        mid = (left + right) / 2;
        
        if(note1[mid] == goal) {
            return 1;
        }
        
        if(note1[mid] < goal) {
            left = mid+1;
        }
        else right = mid-1;
    }
    
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long t; 
    cin >> t;
    
    while(t--) {
        note1.clear();
        cin >> n;
        for(long long i = 0; i < n; i++) {
            long long a;
            cin >> a;
            note1.push_back(a);
        }
        sort(note1.begin(), note1.end());
        
        cin >> m;
        for(long long i = 0; i < m; i++) {
            long long a;
            cin >> a;
            
            cout << binarySerach(a) << "\n";
        }
    }
}

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐