🥇 12757번: 전설의 JBNU

👉🏻 12757번: 전설의 JBNU

'''
다음 M개의 줄에는 아래와 같은 명령이 주어진다.

1 Key Value
- 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다.

2 Key Value
- 해당 Key로 검색된 데이터를 Value로 변경한다. 조건을 만족하는 유일한 Key가 없는 경우 무시한다.

3 Key
- 해당 Key로 검색된 데이터를 출력한다. 조건을 만족하는 Key가 없는 경우 -1을 출력한다.
- 만약 해당하는 Key가 두 개 이상 존재한다면 ?를 출력한다. 모든 출력은 개행을 포함해야 한다.
'''
import sys; input=sys.stdin.readline
from bisect import insort

def find_cloest(keys, target, K):
    if not keys:
        return -1

    # 명령 수행할 때마다 key를 정렬해주는 과정 때문에 병목이 발생 !!
    # 그래서 이분 탐색 라이브러리인 bisect에서 insort 불러와, 이분 탐색으로 key들 정렬하면서 따로 빼주기
    # keys = sorted(keys)
    low, high = 0, len(keys)-1

    if keys[low] >= target and abs(keys[low]-target) <= K:
        return keys[low]
    if keys[high] <= target and abs(keys[high] - target) <= K:
        return keys[high]
    if target < keys[low] or target > keys[high]:
        return -1

    while low <= high:
        mid = (low + high) // 2

        if keys[mid] == target:
            return keys[mid]
        elif keys[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    low_diff, high_diff = float('inf'), float('inf')

    if high >= 0:
        low_diff = abs(keys[high]-target)

    if low < len(keys):
        high_diff = abs(keys[low]-target)

    # 차이가 K보다 큰 경우에는 -1 반환해주기 !
    if low_diff > K and high_diff > K:
        return -1
    
    # 차이가 같으면 결과값이 두 개 이상 생기기에 ? 반환해주기 !
    elif low_diff == high_diff:
        if low_diff <= K:
             return '?'
        else:
             return -1
    elif low_diff < high_diff and low_diff <= K:
        return keys[high]
    elif low_diff > high_diff and high_diff <= K:
        return keys[low]
    else:
        return -1

N, M, K = map(int, input().split())
db = dict()
sorted_keys = []

for _ in range(N):
    key, value = map(int, input().split())
    
    if not key in db:
        db[key] = value
        insort(sorted_keys, key)

for _ in range(M):
    cmd = list(map(int, input().split()))

    if cmd[0] == 1:
        key, value = cmd[1], cmd[2]

        if not key in db:
            db[key] = value
            insort(sorted_keys, key)

    elif cmd[0] == 2:
        key, value = cmd[1], cmd[2]
        cloest_key = find_cloest(sorted_keys, key, K)
        # 유일한 키가 없으면 무시하기로 했기 때문에, -1이거나 ?인 경우는 제외시켜주기
        if cloest_key != -1 or cloest_key != '?':
            db[cloest_key] = value

    elif cmd[0] == 3:
        key = cmd[1]
        # db에 있는 keys들 중에서 key와 가장 가까운 key를 찾아 value를 출력하는 것 !
        # '가장 가까운'이라는 표현은 차이가 가장 작다는 뜻
        # 하나씩 비교할 것이냐 vs 이분 탐색으로 찾을 것이냐
        # 골드 3 정도는 무조건 이분 탐색이지 !
        cloest_key = find_cloest(sorted_keys, key, K)
        print('?' if cloest_key == '?' else -1 if cloest_key == -1 else db[cloest_key])

 

---

왜 이렇게 풀었을까?

• 이분 탐색으로 접근해 본 구현 문제였습니다.
• 처음에는 하나씩 비교해 보려는 시도를 하려다가 10억 개의 키를 상상해보고는 과감히 생각을 접고 바로 이분 탐색으로 넘어갔습니다.
• 기본 골자는 잡는 데에 걸린 시간은 그리 많지 않았는데, 의외로 거리 제한인 K에 따라 분기를 나눠줘야하는 것 때문에 신경을 썼습니다.
• 그리고 처음에는 함수 호출 때마다 정렬을 시켜줬었는데, 해당 방법으로 하니 시간 초과가 발생해 key들만을 따로 이분 탐색으로 정렬해주었습니다. 이때 bisect 모듈의 insort 함수를 사용했습니다.
  • 간단히만 말씀드리자면, insort 함수는 이분 탐색을 이용해 리스트와 특정 key를 넘겨주면 리스트에 key를 적절한 위치에 삽입해줍니다.
• 사용 개념은 골드 초입 수준인데, 정렬 테크닉이 살짝 필요해서 골드 3의 티어가 주어지지 않았나 싶습니다 !