백준 19637 IF문 좀 대신 써줘 파이썬 (시간초과 해결)

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

19637번: IF문 좀 대신 써줘

처음에는 아래와 같이 입력받은 숫자보다 큰수가 나오면 멈추게 완전 탐색 방법으로 구현을 했었다.

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
s=[]
for _ in range(n):
    a,b=input().split()
    b = int(b)
    s.append((a,b))
for _ in range(m):
    t = int(input())
    e=0
    for i in s:
        if t<=i[1]:
            print(i[0])
            e=1
            break
    if e==0:
        print(s[-1][0])

당연하게도 시간초과가 났고 이분탐색을 이용해 풀었다. 이분탐색 부분에서 한가지 부분만 처리해주면 쉽게 풀 수 있는 문제였다.

import sys
input=sys.stdin.readline
def low_bound(t):#이분 탐색 함수.
    st = 0
    en = n-1
    while st<en:
        mid = (st+en)//2
        if t<=s[mid][0]:
            en = mid -1
        else:
            st = mid +1
    if s[st][0]<t:#특수 처리해준 부분(안 해주면 예제 1번같은 경우에 틀림)
        st+=1
    return s[st][1]#그 숫자에 맞는 idx반환
n,m=map(int,input().split())
s=[]#숫자와 idx를 저장할 리스트
dp=[]#글을 저장할 리스트
for i in range(n):
    a,b=input().split()
    b = int(b)
    dp.append(a)
    s.append((b,i))#숫자와 idx저장 why?-> 이분 탐색을 위해 sort를 해줄것이기 때문
s.sort()#같은 숫자면 어떻하죠?->숫자(b)가 같으면 그 뒤에 i를 기준으로 정렬돼서 상관 없다.
for _ in range(m):
    t = int(input())
    print(dp[low_bound(t)])

++다시 생각해보니 내림차순으로 입력받아서 sort부분은 필요 없을거 같다.