[백준/Baekjoon] 10815 숫자 카드 C++ :: Map | Binary Search

 

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

10815번: 숫자 카드

---

1. Logic

- 처음 문제를 딱 봤을 때 map이 먼저 생각났다. map<int, bool>로 선언한 후 접근하면 풀릴 것 같았다.

그리고 이후에 문제의 범위를 봤을때 500000이길래 이분탐색을 사용해서 숫자를 찾아야하는구나 라고 느꼈다.

 

사실 map과 이분탐색 둘다 해봤는데 둘다 통과 된다. 하지만 이분탐색이 시간복잡도가 더 작을 뿐이다.

---

2. Code

map을 이용한 풀이

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> card;
map<int, bool> Map;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        Map.insert({a, true});
    }

    cin >> m;
    for(int i = 0; i < m; i++) {
        int a;
        cin >> a;
        if(Map[a]) cout << 1 << " ";
        else cout << 0 << " ";
    }
}

Binary search를 이용한 풀이

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> card;
vector<int> input;

void binarySearch(int target) {
    int start = 0;
    int end = n - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if(card[mid] == target) {
            cout << 1 << " ";
            return;
        }

        if(card[mid] < target) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    cout << 0 << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        card.push_back(a);
    }

    sort(card.begin(), card.end());

    cin >> m;
    for(int i = 0; i < m; i++) {
        int a;
        cin >> a;
        binarySearch(a);
    }
}

 

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