[백준/Python] 12757. 전설의 JBNU

문제

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

12757번: 전설의 JBNU

문제에서 

M개의 명령문을 처리할 때 "2 num val" 에 대해서 

num으로 검색된 key의 val을 바꾸라고 했는데, 

2개의 key가 모두 존재하는 상황에서 둘다 바꾸는건지, 아니면 아예 안바꾸는건지 명시해주지 않아서 헷갈렸다. 

 

둘다 해보니까 아예 안바꾸는 것이 정답이었다. 문제에서 이 부분을 명확하게 표현해주면 더 좋을 것 같았다. 

풀이

어떤 숫자가 들어왔을 때, JBNU안에서 그 숫자와 가장 가까우면서 K이하로 차이나는 key를 찾아야 했다. 

실제 데이터가 존재하는 key들의 list인 keys를 이분탐색을 통해 삽입해서 항상 정렬된 상태를 유지하도록 했다. 

그리고 어떤 숫자에 대해 가장 가까운 key를 찾을 때에도 이분탐색을 이용했다. 

 

[1, 2, 5] 상태에서 4를 이분탐색하면 2가 나온다. 따라서 2-1 = 1 번째 값과 2번째 값을 비교해서 두 값중에 어떤 것이 4와 더 가까운지 비교하였다. 그리고 두 값과 4의 차이가 동일하면 -2를 return하여 찾은 값이 2개임을 나타내주었다. 

 

이분탐색은 직접 구현하지 않고 python bisect 라이브러리를 이용하였다. 

공식 문서 : https://docs.python.org/ko/3/library/bisect.html

 

기본 input을 썼더니 시간초과가 발생했다. 아래 코드 두줄을 넣어 input대신에 sys.stdin.readline을 사용했다. 

import sys
input = sys.stdin.readline

코드

import bisect
import sys

input = sys.stdin.readline
inputs = input().split()
N = int(inputs[0]) 
M = int(inputs[1])
K = int(inputs[2]) 

jbnu = dict() # key - value 저장할 dict 
keys = [] # key 저장 list, 정렬된 상태, 이분탐색으로 key 삽입 

def addKey(key):
    idx = bisect.bisect_left(keys, key)
    keys.insert(idx,key)
def findKey(num):
    val = jbnu.get(num, -1)
    if val != -1:
        return num
    idx = bisect.bisect(keys, num) # 
    if idx == 0: # 맨 앞
        if abs(keys[idx] - num) <= K:
            return keys[idx]
    elif idx == len(keys): #맨 뒤
        if abs(num - keys[idx-1]) <= K:
            return keys[idx-1]
    else:
        left = num - keys[idx-1]
        right = keys[idx] - num
        if left == right and left <= K:
            return -2 # 두 개 검색됨 
        if left < right and left <= K:
            return keys[idx-1]
        if right < left and right <= K:
            return keys[idx]
    return val # -1 
    
        
for n in range(N):
    inputs = input().split()
    key = int(inputs[0])
    val = int(inputs[1])
    # key - k ~ key + k까지 전부 채우기 
    jbnu[key] = val
    addKey(key)
for m in range(M):
    inputs = input().split()
    if inputs[0] == '1': # INSERT
        key = int(inputs[1])
        val = int(inputs[2])
        jbnu[key] = val
        addKey(key)
    elif inputs[0] == '2': # UPDATE
        num = int(inputs[1])
        val = int(inputs[2])
        key = findKey(num) # 두개가 검색되면 걍 암것도 안바꿈 
        if key >= 0:
            jbnu[key] = val
    else:
        num = int(inputs[1])
        key = findKey(num)
        if key == -2:
            print('?')
        elif key == -1:
            print(-1)
        else:
            print(jbnu[key])

결과