boj 19637

여기서 주요 포인터는 시간제한이 1초라는 점

즉 첫 생각으로는 hashmap 혹은 for로 돌려 찾고 쉽었으나 해당 방식은 o(nm) 이라서 실패

그 후 생각해낸 방식은 바로 바이너리 서치 (이분 탐색 법이다)

문제 해결

우선 배열을 2개 준비하여

WEAK NORMAL STRONG
10000 100000 1000000
다음과 같이 준비한다

후에 입력값
만약 0이 들어 왔다 치면
처음 미드 100000 와 비교 하여 작으니
lower bound 수행 end = mid
다음도 mid 보다 작으니 end = mid 가 되어 10000 weak 가 된다

이런식으로 만약 1000000 이 들어 왔을땐 mid 100000 크니 start = mid +1 이 되어 STRONG이 뽑힌다

전체 코드

private static StringBuilder sb = new StringBuilder();
    public static  void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String[] sArr = new String[n];
        int[] arr= new int[n];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            Integer a = Integer.parseInt(st.nextToken());
            sArr[i] = s;
            arr[i] = a;
        }

        for(int i=0; i<m; i++){
            int num = Integer.parseInt(br.readLine());

            int start = 0;
            int end = n-1;
            while(start< end){
                int mid = (start + end) / 2;


                if(num <= arr[mid]){
                    end = mid;
                }else{
                    start = mid+1;
                }
            }
            sb.append(sArr[end]).append("\n");
        }
        System.out.println(sb);
    }

---

참고로 StringBuilder 를 안하고 String으로 다달이 출력시 시간 초과 발생 한다

전형적인 바이너리 서치 문제 였다.