240427 [BOJ/백준] 19637. IF문 좀 대신 써줘

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

---

나의 코드

1. 딕셔너리에 숫자(전투력)를 키값, 해당하는 칭호를 value값을 넣어 입력한 값에 따라 출력하는 방법(시간초과) 

N, M = map(int, input().split())
dict = {}
for _ in range(N):
    title, power = input().split()
    for i in range(int(power)+1):
        if i not in dict:
            dict[i] = title


for k in range(M):
    cha = int(input())
    print(dict[cha])

 

2. 입력값을 인덱스의 이분탐색을 통해 구하기(성공)

import sys

N, M = map(int, sys.stdin.readline().split())
power_list = []

for i in range(N):
    title, power = sys.stdin.readline().split()
    power = int(power)
    power_list.append([title, power])

for k in range(M):
    power = int(sys.stdin.readline())
    s, e = 0, N
    while s <= e:
        middle = (s+e)//2
        if power > power_list[middle][1]:
            s = middle + 1
        elif power <= power_list[middle][1]:
            e = middle - 1

    ans = s
    print(power_list[ans][0])

 

결과

---

첫번째 방법. 메모리 제한이 조금 커서 여유로울 것 같아서 시간을 줄이기 위해 딕셔너리에 0부터 제일 큰 수까지 해당하는 칭호를 키와 value값으로 넣어주었다. 하지만 알고리즘 분류가 이분탐색이었던 것 만큼 처음부터 끝까지 도는건 역시나 시간초과가 되는 것 같았다.

두번째 방법. 입력값을 그대로 0과 최댓값을 활용해 이분탐색을 하려고 했으나 power_list의 0번째 값에서 power보다 낮은 입력값이 주어졌을 때 해당하는 칭호를 찾지 못했다. 그래서 다른 사람의 코드를 보고 인덱스로 값을 찾고 그것에 해당하는 power값을 비교하는 이분탐색을 진행해서 성공했다!