728x90
SMALL

'''
다음 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의 티어가 주어지지 않았나 싶습니다 !
728x90
LIST
'알고리즘 문제 풀이 > 랜덤 마라톤 (solved.ac)' 카테고리의 다른 글
| 🥇 2230번: 수 고르기 (0) | 2025.02.26 |
|---|---|
| 🥈 24417번: 알고리즘 수업 - 피보나치 수 2 (2) | 2025.01.31 |
| 🥈 2303번: 숫자 게임 (1) | 2024.11.25 |
| 🥈 3060번: 욕심쟁이 돼지 (5) | 2024.10.07 |
| 🥈 5568번: 카드 놓기 (2) | 2024.09.13 |