[C++] BOJ 10815 - 숫자 카드

 

BOJ 10815 - 숫자 카드 (https://www.acmicpc.net/problem/10815)

01. 🔎 문제 탐색

N: 상근이가 가진 숫자 카드의 개수 (첫 번째 배열의 크기)
M: 중복된 카드가 있는 지 확인하기 위한 숫자 카드의 개수 (첫 번째 배열의 크기)

 

즉, N개의 정수가 담긴 배열에 M개의 배열에 담긴 정수가 포함되어 있는 지 아닌 지를 구하여 출력하는 문제

 

* 각 배열의 최대 크기는 500,000
* 정수의 범위는 -10,000,000 ~ 10,000,000

01-1. 가능한 시간 복잡도

M개의 정수가 담긴 배열은 반드시 차례대로 한 번씩 탐색하여 중복인지 아닌지 출력하여야 하므로, 시간복잡도가 O(M) 이상으로 나오게 된다.
시간 제한이 2초로 시간복잡도가 O(M) * x 일 때, 연산 횟수는 2e8(2억)회 미만이 되어야 한다.

 

완전 탐색의 경우 시간복잡도가 O(MN)으로, 최악의 경우 25e10회로 요구되는 최대 연산 횟수를 초과하게 된다.
이분 탐색의 경우 시간복잡도가 O(MlogN)으로, 최악의 경우에도 1e7 미만이다.

 

따라서, 최소한 한 번의 탐색에서 시간복잡도가 O(logN) 이하가 되어야 함을 알 수 있다.

01-2. 알고리즘 선택

• 오름차순 정렬과 시간복잡도가 O(logN) 인 탐색을 할 수 있는 C++에서 제공하는 STL인 Map으로 풀이

02. 📝 코드 설계하기

1. N에 대한 Input을 받아 원소를 Map에 삽입
2. M에 대한 Input을 받아 Map에 해당 원소가 있는 지 탐색

03. 🛠️ 시도별 수정

1회차

• C/C++ 표준 stream 동기화 비활성화를 잊음 --> 입출력 시간 단축을 위해 추가

2회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int N, M;
  map<int, bool> cards;

  cin >> N;
  while(N--){
    int num;
    cin >> num;
    cards[num] = 1;
  }

  cin >> M;
  while(M--){
    int num;
    cin >> num;
    cout << cards[num] << " ";
  }

  return 0;
}