알고리즘/백준
[백준/c++] 19637번: IF문 좀 대신 써줘
녕이
2022. 7. 7. 13:45
728x90
https://www.acmicpc.net/problem/19637
19637번: IF문 좀 대신 써줘
첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭
www.acmicpc.net
예를 들어,
10,000 <= 전투력 : WEAK,
10,000 < 전투력 <= 100,000 : NORMAL,
100,000 < 전투력 <= 1,000,000 : STRONG
전투력에 맞는 칭호를 출력하는 프로그램 작성하자.
#include <iostream>
using namespace std;
string answer;
int n, m;
int value[100000]; //전투력 기준
string title[100000]; //칭호
int binarySearch(int k){
int left = 0, right = n-1;
int mid = 0;
while(left<=right){
mid = (left+right)/2;
if(k <= value[mid]) right = mid-1;
else left = mid+1;
}
if(k > value[mid]) return mid+1;
else return mid;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++) cin >> title[i] >> value[i];
for(int i=0; i<m; i++){
int k;
cin >> k;
cout << title[binarySearch(k)] << '\n';
}
return 0;
}
그냥 for문으로 하면 시간 초과된다..
이분 탐색으로 하면 된다..
칭호 n개를 left = 0, right = n-1로 정하고 중앙 mid를 value 값 인덱스로 해서 이분 탐색을 진행한다.
탐색 후, value [mid] 값이 k보다 크면 mid 인덱스를 한 번 증가시키고 아니라면 mid를 출력해서 title 배열 값을 출력한다.
728x90