문제

입력

출력

예제

idea

하 진짜.. 이것만 생각하면...

처음에는 모든 수를 미리 입력을 다 받은 후 이중 for문을 이용해 칭호와 전투력을 비교하여 출력을 하도록 구현을 하였는데 그렇게 했더니 복잡도가 MxN이 되어 시간이 너무 오래걸려 시간초과가 나오게 되었다.

그래서 고민을 하며 여러가지 정보를 얻은 결과, 모든 변수를 입력받은 후 비교를 하는것이 아닌, 전투력을 입력받을 때 마다 이진탐색을 이용하여 칭호를 바로 탐색하여 append를 해주었다.

하지만 예상치 못한 부분에서 오류가 계속 나왔는데 전투력이 같을 경우 먼저 입력한 칭호를 입력받도록 하는 중복제거 부분에서 오류가 났다. 처음에는 전투력이 같을 경우 다음 칭호를 덮어씌우는 형식으로 진행을 하였더니 런타임 에러 (NoSuchElement)가 발생하였다. 어디서 에러가 났는지 찾는데 시간이 많이 걸렸다.

Code

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 x,y,w=0;
      int num,num_2[];
      
      StringBuilder stringBuilder = new StringBuilder();
    
      x=Integer.parseInt(st.nextToken());
      y=Integer.parseInt(st.nextToken());
      String[] pow = new String[x];

      num_2=new int[x];
     
      for(int i=0;i<x;i++)
      {
    	 st = new StringTokenizer(br.readLine());
         pow[i]= st.nextToken();
         num_2[i]= Integer.parseInt(st.nextToken());
         if(i>0) {      
        	 if(num_2[i]==num_2[i-1]) {
        		pow[i]=pow[i-1];      
            }
         }
       }
      for(int i=0;i<y;i++) {
    	 st = new StringTokenizer(br.readLine());
         num=Integer.parseInt(st.nextToken());
         
         int n = Arrays.binarySearch(num_2,num);         
         if(n<0) {n=-n-1;}
         	
         stringBuilder.append(pow[n]).append("\n");         
      }           
      System.out.println(stringBuilder);
   }
}

결과