코딩테스트
백준 19637: IF문 좀 대신 써줘 [JAVA]
stdio.han
2024. 5. 24. 02:47
[문제 링크]
https://www.acmicpc.net/problem/19637
[난이도]
- Silver 3
[알고리즘]
- 이분탐색
[코드]
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] power;
static String[] title;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
power = new int[N];
title = new String[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
title[i] = st.nextToken();
power[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < M; i++) {
int key = Integer.parseInt(br.readLine());
binarySearch(key);
}
System.out.println(sb);
}
static void binarySearch(int key) {
int left = 0;
int right = N;
int index = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (key <= power[mid]) {
right = mid - 1;
index = mid;
} else if (key > power[mid]) {
left = mid + 1;
}
}
sb.append(title[index]).append("\n");
}
}
[풀이]
찾으려는 key 값이 mid보다 작거나 같을 때마다 index를 갱신해준다. 그리고 while문이 끝났을 경우 갱신해왔던 index를 형식에 맞게 출력해준다.