문제
https://www.acmicpc.net/problem/19637
문제해설
전투력 기준 m개와 전투력 n개가 주어지면
순서대로 기준에 맞는 칭호를 붙여주면 된다.
문제풀이
굉장히 간단해보이는 문제다.
하지만 m개를 다 탐색하는 O(mn)으로 푼다면 시간초과가 발생한다.
그렇기때문에 탐색하는데 log의 시간이 걸리는 방법을 사용해야 한다.
게다가 문자열과 숫자 형태로 입력을 받으니
자료구조 map을 쓴다면 쉽게 해결할 수 있다.
map에 key값으로 숫자를 넣고 value값으로 문자열을 넣어서
lower_bound를 사용해서 탐색하면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int, string>P;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin >> n >> m;
map<int, string>arr;
for (int i = 0; i < n; i++) {
int x; string y;
cin >> y >> x;
arr.insert(P(x, y));
}
map<int, string>::iterator iter;
for (int i = 0; i < m; i++) {
int x; cin >> x;
iter = arr.lower_bound(x);
cout << iter->second << "\n";
}
return 0;
}