[백준] 20551번 Sort 마스터 배지훈의 후계자

출처

https://www.acmicpc.net/problem/20551

20551번: Sort 마스터 배지훈의 후계자

지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 N개의 원소를 가진 배열A$A$를 주고, A의 원소들이 오름차순으로 정렬된 배열B를 만들게 한다. 그다음 M개의 질문을 한다. 각 질문에는 정수 D가 주어진다. 제자들은 주어진 정수D가 B에서 가장 먼저 등장한 위치를 출력하면 된다. 단, D가 B에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.

입력

첫째 줄에 배열A의 원소의 개수 N과 질문의 개수 M이 공백으로 구분되어 주어진다.

다음 줄부터 N줄에 걸쳐 정수 A0,A1,...,AN−1이 주어진다.

다음 줄부터 M줄에 걸쳐 정수 D가 주어진다.

출력

 M개의 질문에 대해서 주어진 D가 B에서 처음으로 등장한 위치를 출력한다. 단, 존재하지 않는다면 -1를 출력한다. (배열에서 가장 앞의 원소의 위치는 0이다.)

제한

• 1 ≤ N≤ 2×10^5
• 1 ≤ M≤ 2×10^5
• -10^9 ≤ A≤ 10^9
• -10^9 ≤ D≤ 10^9

예제

내코드

단순히 배열에 넣어서 순차적으로 찾으려고 하면 시간초과가 나게 됩니다.

그래서 먼저 arr 배열에 넣고 Arrays.sort를 통해서 오름차순 정렬을 수행한 후에 해시 맵을 사용하여 처음 들어오는 값과 인덱스만 키와 값으로 넣어주고 나머지는 continue로 지나칩니다.

이후 출력할 때 해시맵에 있는 값은 해당 값을 출력하고 키에 없는 값만 -1을 출력하면 됩니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        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());

        int[] arr = new int[N];
        for(int i = 0; i<N; i++){
            arr[i]= Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);//오름차순 정렬

        //맵 선언
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i = 0; i<N; i++){
            //arr[i] 값이 이미 들어가 있으면 넘어간다.
            if(hm.containsKey(arr[i])){
                continue;
            }
            //값이 없으면 처음 나온 것이므로 map에 넣어준다.
            else{
                hm.put(arr[i], i);
            }
        }

        for(int i = 0; i<M; i++){
            int input = Integer.parseInt(br.readLine());
            if(hm.containsKey(input)){
                System.out.println(hm.get(input));
            }
            else{
                System.out.println(-1);
            }
        }
    }
}