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

문제

---

19637번: IF문 좀 대신 써줘

코드

---

My answer

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

def binary_search(target, start, end):
    if start > end:
        return level[start]
    mid = (start + end) // 2
    if num[mid] < target:
        return binary_search(target, mid + 1, end)
    else:
        return binary_search(target, start, mid - 1)

level, num = [], []

for i in range(n):
    a, b = input().split()
    level.append(a)
    num.append(int(b))

for i in range(m):
    a = int(input())
    answer = binary_search(a, 0, len(num) - 1)
    print(answer)

Another answer

import sys

rankn,n = map(int, sys.stdin.readline().split())
all = [sys.stdin.readline().split() for _ in range(rankn)]
 
for i in range(n):
    tmp=int(sys.stdin.readline())
    left,right=0,rankn-1
    while(left<=right):
        mid=int((left+right)/2)
        if(tmp>int(all[mid][1])):
            left=mid+1
            mid=left
        else:
            right=mid-1
    print(all[mid][0])

import sys
from bisect import bisect_left
r = sys.stdin.readline
n, m = map(int,r().split())
li, dic = [], {}
for i in range(n):
    x, y = r().split()
    li.append(int(y))
    dic[i]= x
for _ in range(m):
    print(dic[bisect_left(li, int(r()))])

풀이

---

이번 문제도 단순하게 IF문으로 구현하라고 내준 문제가 아니고, 이분탐색을 이용하여 해결하는 문제였다.

우선 일반적인 이분탐색코드를 작성하고, 이 문제의 경우 10000원일 경우 0~10000 사이에 포함되지 않기 때문에 =조건을 이용해서 특정 숫자를 찾는 방식이 아니라, 특정 숫자가 포함된 곳을 찾는 방식으로 짜면 됐다.

나는 재귀를 이용한 이분탐색 코드를 짰고, 다른 방법으로는 파이썬의 이분탐색 bisect의 bisect_left를 이용해서 찾을 수도 있고 혹은 반복문을 이용한 이분탐색 코드도 작성할 수 있었다.

이 여려가지 방법 모두 익숙해져야 혹시 모를 상황에 대비할 수 있을 것 같다.