[백준 19637] IF문 좀 대신 써줘

🍎[백준 19637] 제목

문제링크

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

19637번: IF문 좀 대신 써줘

 

 

⚾ 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
tag = []
for _ in range(n):
    a, b = map(str, input().split())
    tag.append((int(b), a))
users = [int(input()) for _ in range(m)]

# 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.
# ==> lower_bound!


def solution(power):
    start, end = 0, len(tag)

    while start < end:
        mid = (start+end)//2
        if tag[mid][0] < power:
            start = mid+1
        else:
            end = mid
    print(tag[end][1])


for i in users:
    solution(i)

 

🔔 해결 과정 & 깨달은 점

- 처음에 어떻게 풀어야 할 지 고민이 되었다. 단순한 문제이지만 입력값이 칭호의 개수는 (1 ≤ N ≤ 10^5)이고, 캐릭터들의 개수는 (1 ≤ M ≤ 10^5)였다. 캐릭터마다 for문을 돌면서 칭호를 찾는다면 시간을 초과할 것이다. 

- 문제를 다시 찬찬히 읽어보니 "어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다."라고 되어 있었다. 이는 lower_bound를 사용해라! 라는 말처럼 보였다.

- 따라서 lower_bound를 사용해서 풀었더니 쉽게 풀렸다.