[백준 10815 C++] 숫자 카드

백준 10815번 문제 및 풀이입니다. 집합과 맵으로 분류되어 있고 등급은 실버5입니다.

 

목차

 

 

---

 

 

[백준 10815 C++] 숫자 카드

 

---

해결 전략

배열 2개를 만들어 비교해준다.

 

 

---

 

코드

 

#include <iostream>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, M;
    cin >> N;
    int *arr1 = new int [N];        
 
    for (int i = 0; i < N; i++)
    {
        cin >> arr1[i];
    }
 
    cin >> M;
    int *arr2 = new int [M];
 
    for (int i = 0; i < M; i++)
    {
        cin >> arr2[i];
    }
 
    for (int i = 0; i < M; i++)
    {
        bool binary = 0;
 
        for (int j = 0; j < N; j++)
        {
            if (arr2[i] == arr1[j])
                binary = 1;
        }
 
        cout << binary << " ";
    }
 
    delete[] arr1;
    delete[] arr2;
 
    return 0;
}

arr1과 arr2를 동적배열로 할당한다.

arr2를 arr1 숫자들과 비교하여 같은 숫자가 나올 시 1로 바꾸어 출력한다.

 

문제점!

for문이 이중으로 돌아 시간복잡도 O(N^2)이다. 컴파일러는 무리없이 돌아가고 입출력이 잘 되지만 백준에서는 시간초과로 나온다. 시간복잡도가 낮은 코드로 다시 작성해야 한다.

 

---

 

더 나은 코드

벡터에 가지고 있는 숫자 카드 N개를 넣어준다. 다 넣어준 후  sort()로 정렬해준다. 비교해야 되는 숫자 카드를 넣어주면서 그 전에 만든 벡터와 비교하며 binary_search()를 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, M, number, Mnumber;
    cin >> N;
 
    vector<int> v;   
 
    for (int i = 0; i < N; i++)
    {
        cin >> number;
        v.push_back(number);
    }
    sort(v.begin(), v.end());
 
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> Mnumber;
        cout << binary_search(v.begin(), v.end(), Mnumber) << ' ';
    }  
 
    return 0;
}
 

 

 

vector를 사용하여 내장 함수인 sort(), binary_search() 를 사용하였다.

 

 

 

---

 

참고자료

 

binary_search() 

https://dev-mystory.tistory.com/222

C++ - Algorithm 헤더 파일 binary_search(), lower_bound(), upper_bound()

 

https://swblossom.tistory.com/56

[C++] 벡터(vector)와 메소드들(erase, insert) 그리고 binary search(lower_bound, upper_bound)