[ baekjoon ] 전설의 JBNU 12757번 ( python )

문제

백준 12757 전설의 JBNU 풀이 ( 파이썬 )

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

12757번: 전설의 JBNU

 

풀이

주석에도 적었지만 key들을 저장하는 keys리스트를 선언했는데 넣을 때부터 정렬하여 넣는다. 이때 이분 탐색을 사용하여 삽입했다.

findkey 함수는 k값안에 내가 원하는 key가 있는지 확인하는 것인데,

-2를 리턴할 때는 양쪽에 같은 k범위의 키가 두 개 있는 것이므로 ?를 출력할 때 쓰고

-1를 리털할 때는 만족하는 키가 없으므로 -1를 출력할 때 쓴다.

나머지 다른 것을 리턴하는 것은 만족하는 키가 있다는 것이므로 해당하는 키에 대한 value를 출력한다.

 

출력 예제를 그림으로 보면

초기 삽입했을 때 이런 값을 갖게 된다 keys를 보면 정렬이 되어있는데 언급했듯 이분탐색으로 삽입했기 때문,

다음 명령들을 보면

처음 3 2를 수행할 때

tmpkey=findkey(arr[1])로 올바를 키가 있는 것을 확인하는 것인데

findkey 함수를 통해서 2는 1과 가까우므로 1를 찾아서 tmpkey값이 되고

10을 출력하게 된다.

이런식으로 key를 찾고 삽입, 수정, 출력을 진행하게 된다.

import sys
import bisect

input=sys.stdin.readline

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

# 이진탐색으로 key들을 저장할 리스트
keys=[]

# 정확한 key와 value를 저장하기 위한 dict()
dic=dict()

# 이진탐색으로 키를 삽입함(순서대로 넣기위함)
def putkey(key):
    bisect.insort(keys,key)
    return

# k범위 안의 키가 있는지 찾는 것
def findkey(key):
    idx=0
    val=dic.get(key,-1)
    leng=len(keys)
    if val != -1:
        return key
    else:
        key_idx=bisect.bisect(keys,key)
        # 입력한 key가 들어갈 예상될 곳이 첫 번째 인덱스일 때
        if key_idx==0:
            if abs(keys[0]-key)<=k:
                return keys[0]
        # 입력한 key가 들어갈 예상될 곳이 마지막 인덱스일 때
        elif key_idx==leng:
            if abs(keys[key_idx-1]-key)<=k:
                return keys[key_idx-1]
        else:
            # 답이 ?가 나와야함
            if keys[key_idx]-key==key-keys[key_idx-1]:
                return -2
            # 답 1개(왼쪽 키가 조건에 맞음)
            if keys[key_idx]-key>key-keys[key_idx-1]:
                if key-keys[key_idx-1]<=k:
                    return keys[key_idx-1]
            # 답 1개(오른쪽 키가 조건에 맞음)
            if keys[key_idx]-key<key-keys[key_idx-1]:
                if keys[key_idx]-key<=k:
                    return keys[key_idx]

    # 답이 1이 나와야함
    return -1


for i in range(n):
    key,val=map(int,input().split())
    dic[key]=val
    putkey(key)

for i in range(m):
    arr=list(map(int,input().split()))
    if arr[0]==1:
        # 값들을 저장한다
        # 여기는 정확한 키 밸류값
        dic[arr[1]]=arr[2]
        # 정확한 키를 저장
        putkey(arr[1])
    if arr[0]==2:
        tmpkey=findkey(arr[1])
        if tmpkey==-1 or tmpkey==-2:
            continue
        else:
            dic[tmpkey]=arr[2]
    if arr[0]==3:
        tmpkey=findkey(arr[1])
        if tmpkey==-1:
            print(-1)
        elif tmpkey==-2:
            print("?")
        else:
            print(dic[tmpkey])