[백준] 전설의 JBNU

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

12757번: 전설의 JBNU

Java의 TreeMap을 활용하여 풀긴 풀었는데 파이썬으로는 무수한 시간초과를 겪고난 뒤에 해결하여 현재는 미해결 문제로 분류하였습니다. 아이디어는 Map의 key들을 이분탐색하면서 대체 키를 찾아주면 됩니다. 포인트는 key들을 정렬된 상태로 유지해야하는데 Java는 TreeMap에서 기능들을 제공하지만 Python에서는 매번 Key들을 정렬해야해서 시간초과가 발생하게 됩니다. 추후에 Python으로 재풀이해보도록 하겠습니다.

 

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, k;
	static StringBuilder sb = new StringBuilder();

	static TreeMap<Integer, Integer> tm = new TreeMap<>();
	
	 public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		// 초기화
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int key = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			tm.put(key, value);
		}
		
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			
			int cmd = Integer.parseInt(st.nextToken());
			
			if (cmd == 1) {
				int key = Integer.parseInt(st.nextToken());
				int value = Integer.parseInt(st.nextToken());
				
				tm.put(key, value);
			} else if (cmd == 2) {
				int key = Integer.parseInt(st.nextToken());
				int value = Integer.parseInt(st.nextToken());
				
				updateKey(key, value);
			} else {
				int key = Integer.parseInt(st.nextToken());
				print(key);
			}
		}
		System.out.println(sb);
	}
	 
	static void print(int key) {
		Integer rightKey = tm.ceilingKey(key);
		Integer leftKey = tm.floorKey(key);
		
		if (rightKey == null) {
			if (key - leftKey <= k) {
				sb.append(tm.get(leftKey) + "\n");
			} else {
				sb.append(-1 + "\n");
			}
			return;
		}
		
		if (leftKey == null) {
			if (rightKey - key <= k) {
				sb.append(tm.get(rightKey) + "\n");
			} else {
				sb.append(-1 + "\n");
			}
			return;
		}
		
		int rightDiff = rightKey - key;
		int leftDiff = key - leftKey;
		
		if (rightDiff <= k && leftDiff <= k && rightKey == leftKey) {
			sb.append(tm.get(leftKey) + "\n");
		} else if (rightDiff < leftDiff && rightDiff <= k) {
			sb.append(tm.get(rightKey) + "\n");
		} else if (leftDiff < rightDiff && leftDiff <= k) {
			sb.append(tm.get(leftKey) + "\n");
		} else if (rightDiff == leftDiff && rightDiff <= k) {
			sb.append("?\n");
		} else {
			sb.append(-1 +"\n");
		}
	}
	 
	static void updateKey(int key, int value) {
		Integer leftKey = tm.floorKey(key);
		Integer rightKey = tm.ceilingKey(key);
		
		if (leftKey == null) {
			int rightDiff = rightKey - key;
			
			if (rightDiff <= k) {
				tm.put(rightKey, value);
				return;
			}
		}
		
		if (rightKey == null) {
			int leftDiff = key - leftKey;
			
			if (leftDiff <= k) {
				tm.put(leftKey, value);
				return;
			}
		}
						
		int rightDiff = rightKey - key;
		int leftDiff = key - leftKey;
		
		if (rightKey == leftKey && rightKey == key) {
			tm.put(leftKey, value);
		} else if (rightDiff < leftDiff && rightDiff <= k) {
			tm.put(rightKey, value);
		} else if (leftDiff < rightDiff && leftDiff <= k) {
			tm.put(leftKey, value);
		}
	}
}