문제 풀이

입력되는 숫자들의 제한을 보면 10만, 10억.. "칭호는 전투력 상한값의 비내림차순으로 주어진다" 등 이분탐색으로 풀어야 한다는 힌트가 조금씩 보인다
그러므로 이분탐색으로 풀면된다.

문제 링크

boj/19637

소스코드

PS/19637.java

       import java.io.*;
    import java.util.*;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static String [] arr = new String[100001];
        static int [] arr2 = new int[100001];
        public static void main(String[] args) throws IOException {
            int n,m;
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            for(int i=0;i<n;i++)
            {
                st = new StringTokenizer(br.readLine());
                arr[i] = st.nextToken();
                arr2[i] = Integer.parseInt(st.nextToken());
            }
            for(int i=0;i<m;i++)
            {
                long num = Long.parseLong(br.readLine());
                int l=0, r= n-1;
                while(l<=r)
                {
                    int mid = (l+r) / 2;
                    if(arr2[mid] < num)
                    {
                        l= mid + 1;
                    }
                    else {
                        r = mid - 1;
                    }
                }
                bw.write(arr[l]+"\n");
            }
            bw.flush();

        }

    }