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

걸린 시간: 15m05s

문제

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

문제 접근 방법

처음에는 map<int, int>를 사용해서 입력받은 카드와 개수를 같이 구할려고 했었다.

1  for(int i=0; i<n; ++i) {
2    int t; 
3    cin >> t;
4    (nmap[t])++;
5  }
6
7  cin >> m;
8  for(int i=0; i<m; ++i) {
9    int t;
10    cin >> t;
11    mmap.push_back(make_pair(t, nmap[t]));
12  }

그러면 출력은 그냥 해당 key의 value값을 출력하면 된다.

1  const int SIZE = mmap.size();
2  for(int i=0; i<SIZE; ++i) {
3    cout << (mmap[i]).second << ' ';
4  }
5  cout << endl;

하지만 시간 초과가 나왔다... 그래서 고민을 하면서 이 함수 저 함수 보다가 upper_bound()와 lower_bound()들을 알게되었다. 1 1 1 2 3 이렇게 있을 때 upper_bound(1)이 3번째 인덱스의 1을, lower_bound(1)이 0번째 인덱스의 1의 위치를 반환하므로 두 위치의 차를 구하면 1이 몇 개 있는지 알 수 있다.

C++ 코드

1#include <bits/stdc++.h> 
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5#define endl '\n'
6
7int main() {
8  int n,m,t;
9  scanf("%d", &n);
10  vector<int> v;
11
12  for(int i=0; i<n; ++i) {
13    scanf("%d", &t);
14    v.push_back(t);
15  }
16
17  sort(v.begin(), v.end());
18
19  scanf("%d", &m);
20  for(int i=0; i<m; ++i) {
21    scanf("%d", &t);
22    int cnt = upper_bound(v.begin(), v.end(), t) - lower_bound(v.begin(), v.end(), t);
23    printf("%d ", cnt);
24  }
25  printf("\n");
26
27  return 0;
28}

시간 복잡도

• 숫자 카드 N개의 입력 - O(N)
• sort() - O(NlogN)
• upper_bound() & lower_bound() M번 = O(MlogN)
• 최종 시간 복잡도: O(N) + O(NlogN) + O(MlogN)

공간 복잡도

• 숫자 카드 N개를 저장 - O(N)
• 최종 공간 복잡도: O(N)