[백준] 10815번: 숫자 카드 풀이 및 해설(C++)

 

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

10815번: 숫자 카드

 

C++로 작성한 백준 문제 10815번 숫자 카드에 대한 문제 풀이다.

실버 5 문제로 이분탐색, 자료구조, 정렬, 해싱이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

---

문제 파악하기

1. 결국 상근이가 해당 카드를 가지고 있는지 여부는 직접 비교해야 한다.
2. 정렬을 사용하면 더 빠르고 편하게 비교할 수 있을 것이다.
3. 그냥 일일이 다 찾는다고 해보자. 그러면 for문 2개로 500000*500000개 항목을 비교하게 되고,250억 이므로, 1억당 1초 걸린다고 했을 때 250초로 시간초과가 나온다. 더 빠른 방법이 필요하다.

 

데이터를 정렬하고, 이분탐색으로 값을 비교해 출력한다.

 

 

 

 

 

---

 

코드 및 설명

#include <iostream>
#include<algorithm>
using namespace std;
int main()
{ 
    int anumber,bnumber;
    int check;
    int low,mid,high;
    cin >>anumber;
    int acard[anumber];
    
    for(int i=0; i<anumber; i++){
        cin>>acard[i];
    
    }
    sort(acard,acard+anumber);

    cin >>bnumber;
    int bcard[bnumber];
    
    for(int j=0; j<bnumber; j++){
        cin>>bcard[j];
    }
    
    
    for(int k=0; k<bnumber; k++){
        check=0;
        low=0;
        high=anumber-1;
        while(low<=high){
           mid=(low+high)/2;
           if(bcard[k]==acard[mid]){
               check=1;
               break;
           }
           if(bcard[k]>acard[mid]){
               low=mid+1;
           }
           else{
               high=mid-1;
           }

        }
    
        cout<<check<<' ';
    }

    return 0;
}

 

 

sort() 함수로 값을 정렬한 후 이분탐색을 통해 값이 일치하는지 아닌지 찾아준다.

---

 

해메었던 부분

이진탐색 안 하고 일일이 하다가 시간초과가 났다. 그리고 다 풀어놓고 변수 이름을 착각해 오류가 났다. 변수이름을 제대로 정해야 될 것 같다.

 

 

 

 

 

---

 

마무리

순서가 중요하지 않은 데이터가 들어온다면, 정렬하는 것이 좋다. 일단 정렬시키고 이분탐색이나 다른 탐색으로 빠르게 답을 찾아내자