[ baekjoon ] #10815 숫자 카드

백준 #10815 숫자 카드

문제

---

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

💡Idea - map 자료구조 이용

1. 상근이가 가지고 있는지 어떻게 판단할까?
   • map을 이용하면 빠르지 않을까?
     → 상근이가 가지고 있는 숫자를 map에 저장해두자 !
     → 찾아야할 숫자의 value 값이 0이 아니라면 존재하는 숫자이므로 1을, 0이라면 존재하지 않으므로 0을 출력

[ SourceCode - map ]

#include <iostream>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	// 1. 입력 받기
    int N, M;
    cin >> N;
    map <int, int> find;
    for(int i=0; i<N; i++) {
        int num;
        cin >> num;
        find[num]++;
    }
	// 2. 존재하는 숫자인지 확인하기
    cin >> M;
    for(int i=0; i<M; i++) {
        int n;
        cin >> n;
        if(find[n]) cout << "1 ";
        else cout << "0 ";
    }

    return 0;
}

💡Idea - binary_search

1. 상근이가 가지고 있는지 어떻게 판단할까?
   • 우선 상근이가 가지고 있는 카드를 정렬하자
   • 중간값을 구하고 찾을값보다 크다면 rt 값을 mid-1로, 작다면 lt를 mid+1로 바꿔주자 !

[ SourceCode - binary_search ]

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

using namespace std;

// 숫자 카드 이분탐색하기
void find_card(int key, vector<int> &card) {
    int lt = 0, rt = card.size() - 1;
    int mid = (lt + rt) / 2;
    while(lt <= rt) {
        mid = (lt + rt) / 2;
        if(card[mid] == key) {
            cout << "1 ";
            return;
        }
        else if(card[mid] < key) {
            lt = mid + 1;
        }
        else if(card[mid] > key) {
            rt = mid -1;
        }
    }
    cout << "0 ";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 1. 입력 받기
    int N, M;
    cin >> N;
    vector <int> card(N);
    for(int i=0; i<N; i++) {
        cin >> card[i];
    }
   
    sort(card.begin(), card.end()); // 카드 오름차순 정렬

    // 2. 찾을 숫자를 입력받고 찾기
    cin >> M;
    for(int i=0; i<M; i++) {
        int n;
        cin >> n;
        if(n < card[0] || n > card[N-1]) {
            cout << "0 ";
            continue;
        }
        find_card(n, card);
    }

    return 0;
}

Feedback

---

1. 시간초과가 나서 이유를 찾지 못했다.
   → 최악의 상황에서도 숫자카드가 500,000개이고 구해야할 숫자도 500,000개이므로 시간초과가 날 것 같진 않았다.
   → 찾아보니 cin과 cout을 번갈아가면서 하여 cout에 매번 flush 연산이 발생하는 것이 원인이었다.
   → cin.tie(NULL); 로 해결 !

Remind

---

• cin.tie(NULL);
  → cin을 cout으로부터 untie 한다는 의미
• tie
  : stream에서 입출력 요청이 오기 전에 stream을 flush 시킨다.
  : program이 user에게 입력을 요구하기 전에 output flush 시킨다.
• untie
  : output이 flush되지 않은 상태로 user에게 입력을 요구한다.

⛧ cout과 output은 buffer가 가득차거나 flush 되기 전까지 출력하지 않는다 !
→ untie시 cin으로 입력 받기 전에 출력을 하고 싶다면 수동적으로 flush 해줘야한다.