백준_19637_파이썬

문제 핵심

주어진 것
1. 각 전투력 별 칭호
2. N과 M의 범위
3. 전투력 별 칭호가 주어지는 순서(비내림차순)
내림차순이 아님
4. N과 M의 범위

알고리즘
전투력에 따른, 칭호

출력
칭호만 출력

구현

1. 전투력 별 칭호를 저장한다. (같은 전투력이면 먼저 입력된 칭호를 출력한다.)
2. 전투력이 입력되면 칭호를 print한다.

생각보다 간단한 구현 문제라고 생각했지만, 세 번의 시간초과를 겪었다.

• N과 M의 범위를 확인해야 했다.
  입력받은 전투력 별로 칭호를 확인하자 갯수가 최대 N M = 10^5 10^5 = 10^10이 걸렸다.
• 중복으로 입력된다면 먼저 입력된 칭호를 반환해야 한다.

1. set으로 중복 입력값을 걸러서 저장(칭호와 전투력 저장단계에서)
2. print할때 가장 첫번째를 반환(출력시 저장된 값 중 첫번째 꺼 출력)
   -> set의 크기를 늘리는 것(출력시 set조회) vs set의 크기를 애초에 줄이는 것(저장시 set 조회)

시간 복잡도 상에서는 둘이 동일하지만, 후자의 방식이 리스트를 더욱 간결하게 만들어 유지하므로 후자의 방식을 선택하였습니다.

놓칠 수 있는 부분

1. 전투력이 같은 칭호가 있다면, 먼저 입력된 칭호 반환
2. brute force로 구현하면 시간 초과가 나온다. (N과 M의 범위를 확인)
3. sys.stdin.readline으로 읽지 않고 input()으로 읽게되면 시간초과가 나온다.

import sys
input = sys.stdin.readline

# N: number of titles, M: number of characters
N, M = map(int, input().split())

title_power = []
seen_powers = set()
for _ in range(N):
    title, power = input().split()
    power = int(power)
    if power not in seen_powers:
        title_power.append((power, title))
        seen_powers.add(power)

# Sort the list by power values
title_power.sort()

def binary_search(power):
    left, right = 0, len(title_power) - 1
    while left <= right:
        mid = (left + right) // 2
        if title_power[mid][0] >= power:
            right = mid - 1
        else:
            left = mid + 1
    return title_power[left][1] if left < len(title_power) else 'No suitable title'

for _ in range(M):
    power = int(input())
    print(binary_search(power))