백준-19637(파이썬)

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

19637번: IF문 좀 대신 써줘

 

문제생각

처음에는 n번 입력 받는 값을 dictionary 형태로 저장하고 m개의 값이랑 비교를 하면 될 것 같았습니다.

하지만 시간 제한과 입력받는 값의 범위를 보아하니 위의 방법은 통하지 않겠다고 생각하였습니다.

그래서 리스트에 인덱스도 사용하고자 했지만 입력받는 범위도 10^9 라서 메모리초과가 날거 같았습니다.

 

한참 고민하다가 알고리즘 분류를 보았는데 이진탐색을 사용해야하는 문제였던 것이였습니다.

 

하지만 이진탐색을 어떻게 사용할까 고민을 해보았는데 그냥 일반 이진탐색과 다를게 없었습니다.

 

다만 이진탐색에서 탐색의 시작 지점과 끝 지점이 서로 교차되었을 경우 찾고자 하는 값이 리스트에 없고 그 사이에 있는 값이라는 것을 의미합니다. 그래서 교차지점의 해당하는 칭호를 정답 리스트에 넣어주면 되는 것이였습니다.

 

 

문제코드

import sys
input=sys.stdin.readline

n, m=map(int, input().split())
dic={}
name, ans=[], []
for _ in range(n):
    a, b=input().split()
    if int(b) not in dic.keys(): 
        dic[int(b)]=a #dictionary 형태
        name.append(int(b)) # 상한값 입력

def find(n_list, num, start, end):

    while start<=end:
        mid=(start+end)//2
        if n_list[mid]==num:
            ans.append(dic[num])
            return
        elif num<n_list[mid]:
            end=mid-1
        elif num>n_list[mid]:
            start=mid+1

    ans.append(dic[n_list[start]])
    return

#m개의 입력
for _ in range(m):
    score=int(input())
    find(name, score, 0, len(name)-1)

#출력부분
for i in ans:
    print(i)

 

"아직 실력이 부족하여 문제 해결에 있어 코드가 매끄럽지 못한 점 양해부탁드립니다..ㅎ"