[파이썬]baekjoon 20551: Sort 마스터 배지훈의 후계자

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

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

---

정렬 알고리즘을 이용하여, 문제를 풀면 된다. 

 

어떤 정렬인지는 상관없으나, 본인은 이진탐색을 이용하여 풀었음.

 

a는 같은 숫자가 여러개가 있을 수 있으며, 같은 숫자가 많다면 가장 작은 index를 출력해야 함을 주의!

import sys
input = sys.stdin.readline
n, m =list(map(int,input().split()))
a = [int(input()) for _ in range(n)]
d = [int(input()) for _ in range(m)]
b = sorted(a)

def search(d):
    st = 0
    ed = n-1
    while st <= ed:
        mid = (st + ed) //2
        if b[mid] ==d:
            if mid >0:
                if b[mid -1] < b[mid]:
                    return mid
                else:
                    ed = mid -1
            else:
                return mid
        elif b[mid] > d:
            ed = mid - 1
        else:
            st = mid + 1
    return -1

for i in d:
    print(search(i))