[백준][이진탐색] 19637. IF문 좀 대신 써줘

19637. IF문 좀 대신 써줘

• 내 풀이
  • 시간초과

#10000 이하: weak
#100000 이하 normal
#1000000 이하 strong

n,m=map(int,input().split())
pname=[]
power=[]

for _ in range(n):
    #칭호, 전투력 상한값
    name, p= input().split()
    pname.append(name)
    power.append(int(p))

result=[]
for _ in range(m):
    #각 캐릭터별 전투력
    fight=int(input())
    for i in range(n):
        if i==0:
            if fight<=power[0]:
                print(pname[0])
                break
        if power[i-1]<fight<=power[i]:
            print(pname[i])

 

• 풀이2
  • 이진탐색
  • 딕셔너리 이용 -> 시간초과
  • value만 뽑아서 리스트로 만드는 시간이 오래걸리는건가?

#10000 이하: weak
#100000 이하 normal
#1000000 이하 strong
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
power={}
for i in range(n):
    pname, maxPower=input().split()
    if list(power.values()) and list(power.values())[-1]==int(maxPower):
        continue
    power[pname]=int(maxPower)

pk=list(power.keys())
pv=list(power.values())

def binary(check):
    left=0
    right=len(pk)-1
  
    while left <= right:
        mid=(left+right)//2
        if check<=pv[mid]:
            right=mid-1
        else:
            left=mid+1
    result.append(pk[right+1])

result=[]
for i in range(m):
    check=int(input())
    binary(check)

for r in result:
    print(r)

 

• 풀이 3
  
  • 배열 이용 
  • in , not in -> 시간초과

#10000 이하: weak
#100000 이하 normal
#1000000 이하 strong
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
power=[]
name=[]
for i in range(n):
    pname, maxPower=input().split()
    if int(maxPower) not in power:
        name.append(pname)
        power.append(int(maxPower))


def binary(check):
    left=0
    right=len(power)-1
  
    while left <= right:
        mid=(left+right)//2
        if check<=power[mid]:
            right=mid-1
        elif check >power[mid]:
            left=mid+1
    print(name[right+1])
  
for i in range(m):
    check=int(input())
    binary(check)

 

• 다른 사람 풀이 (최종 정답)
  • 맨마지막 값 탐색으로 바꿔야 시간초과 안난다

#10000 이하: weak
#100000 이하 normal
#1000000 이하 strong
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
power=[]
name=[]
for i in range(n):
    pname, maxPower=input().split()
    if power and power[-1]==int(maxPower):
        continue
    name.append(pname)
    power.append(int(maxPower))


def binary(check):
    left=0
    right=len(power)-1
  
    while left <= right:
        mid=(left+right)//2
        if check<=power[mid]:
            right=mid-1
        elif check >power[mid]:
            left=mid+1
    print(name[right+1])
  
for i in range(m):
    check=int(input())
    binary(check)