칭호는 전투력 상한값의 비내림차순으로 주어진다. = 오름차순 이란 말인가??
상당히 찝찝하지만... 오름차순으로 이해하고 문제를 풀었다.
이 문제에서 주의할 점은 입출력이 많기 때문에 내가 평소에 애용하는 Scanner/System.out.println을 써 버리면 시간초과가 난다는 점이다.
BufferedReader/BufferedWriter를 써버릇 해야 하는데.. 길고 귀찮아서 굳이 틀려야 바꿔보게 된다... 담엔 입출력 갯수부터 파악하자...ㅠ
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
String name[] = new String[n];
int power[] = new int[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
name[i] = st.nextToken();
power[i] = Integer.parseInt(st.nextToken());
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < m; i++) {
int characterPower = Integer.parseInt(br.readLine());
bw.write(getName(characterPower, n, power, name) + "\n");
}
bw.flush();
br.close();
}
private static String getName(int characterPower, int length, int[] power, String[] name) {
int start = 0;
int end = length - 1;
int answer = end;
while (start <= end) {
int mid = (start + end) / 2;
if (characterPower <= power[mid]) {
answer = Math.min(mid, answer);
end = mid - 1;
} else {
start = mid + 1;
}
}
return name[answer];
}
}
'알고리즘 공부 > boj' 카테고리의 다른 글
boj 20164: 홀수 홀릭 호석 (0) | 2021.03.24 |
---|---|
boj 11663: 선분 위의 점 (0) | 2021.03.17 |
boj 2805: 나무 자르기 (0) | 2021.03.16 |
boj 2417: 정수 제곱근 (0) | 2021.03.15 |
boj 1789: 수들의 합 (1) | 2021.03.15 |