[Python][백준/BOJ] 19637번 : IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

 

내 코드

시간 초과된 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lv ={}
for _ in range(n):
    a, b = input().split()
    lv[a] = int(b)
lv = sorted(lv, key = lambda x : x[1])

for i in range(m):
    prev =-1
    arr = [[]for _ in range(m)]
    power = int(input())
    for key, value in lv:
        if prev <power <= value:
            prev = value
            arr[i] = key
            continue
    print(arr[i])

 

통과된 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lv = [input().split() for _ in range(n)]

def bisect(i):
    left =0
    right = len(lv)-1
    result =0
    while left <= right:
        mid= (left+right)//2
        if i <= int(lv[mid][1]): #중간 값보다 해당 수가 작을 때
            right = mid-1
            result = mid
        else: #수가 작을 떄
            left = mid+1
    return lv[result][0]

for _ in range(m):
    power = int(input())
    print(bisect(power))

 

코드 리뷰

처음에는 제목이 'IF문 좀 대신 써줘' 라서 간단하게 if문으로 구현하는 문제인 줄 알았다. 하지만 막상 풀어보니 시간초과가 떠서, 이분탐색으로 시간을 줄여서 해결해야 하는 문제였다.

그래서 bisect 라는 함수를 만들어주었다. bisect에서 값을 비교하면서, left 와 right의 값이 일치할 때가 답이 되는 것이다.

이 문제에서는 lv 배열이 등장하는데, 이 배열은 rank를 구분하는 조건이 저장되어 있다.

lv는 [[칭호, 값] , [칭호, 값] ...] 이렇게 구성되어 있다.

 

현재 수 <= 랭킹을 구분하는 조건 값

이분탐색은 중간값을 찾아낼 수 있기 때문에 해당 방식으로 중간을 찾아내면 된다. 

함수 안에서는 계속해서 현재 수가 lv 배열에 들어있는 조건 값보다 작은지 확인한다. 만약 조건의 중간 값보다 작다면 right를 mid-1 해주면 되고, 크다면 left를 mid+1 해주면 된다.

중간 값은 곧 해당 값이 속해있는 조건 값을 의미하기 때문에 result = mid 를 해준다.

 

그리고 계속해서 틀렸던 이유는 내가 lv = sorted(lv, lambda x:x[1])를 하여 lv 배열을 값에 따라 정렬을 했기 때문이었다. 예제의 답은 올바르게 출력됐지만, 이로 인해서 계속해서 오답으로 간주되었다. 

이는 조건 중에 'M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.' 라는 조건을 충족하지 못해서 오류가 뜬 것으로 생각한다.