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

문제

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

입력

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

다음 줄부터 N$N$줄에 걸쳐 정수 A0,A1,...,AN−1$A_0, A_1, ... , A_{N-1}$이 주어진다.

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

출력

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

제한

• 1 ≤ N$N$ ≤ 2×105
• 1 ≤ M$M$ ≤ 2×105
• -109 ≤ Ai$A_i$ ≤ 109
• -109 ≤ D$D$ ≤ 109

예제 입력 1 복사

5 5
9
0
-1
3
2
-1
10
5
9
0

예제 출력 1 복사

0
-1
-1
4
1

예제 입력 2 복사

8 4
3
3
4
9
2
5
3
4
3
10
4
2

예제 출력 2 복사

1
-1
4
0

출처

University > 인하대학교 > 2020 인하대학교 프로그래밍 경진대회(IUPC) B번

• 문제를 검수한 사람: august14, bsgreentea, dlstj0923, dongwoo338, rhs0266, tony9402, tyoungs
• 문제를 만든 사람: polohee81

알고리즘 분류

• 자료 구조
• 정렬
• 이분 탐색

---

import sys


def binary_search(target):
    start, end = 0, n - 1
    ans = -1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            if end == start:
                return mid
            else:
                ans = mid
                end = mid - 1
        elif nums[mid] > target:
            end = mid - 1
        elif nums[mid] < target:
            start = mid + 1
    return ans


n, m = map(int, sys.stdin.readline().split())
nums = sorted([int(sys.stdin.readline()) for _ in range(n)])
for _ in range(m):
    print(binary_search(int(sys.stdin.readline())))