12757번: 전설의 JBNU [JAVA]

문제 설명

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

12757번: 전설의 JBNU

[문제]

 전설의 프로그래머 윤준하는 독자적인 데이터베이스 시스템 JBNU(Jeong Bo Neoh Um)를 만들었다.

 준하가 생각한 데이터베이스의 기본 골자는 데이터에 접근하기 위한 Key와 그 데이터를 나타내는 Value로 구성되어 있다. 사용자는 Key를 알고 있어야만 원하는 데이터에 접근할 수 있다.

 하지만 준하는 건망증이 심해 Key를 매번 잊어버리기 일쑤였다. 따라서 준하는 JBNU를 개조하여 잘못된 Key를 입력하더라도 그 잘못된 Key와 제일 근접한 Key를 찾아주는 메커니즘을 도입하였다.

 Key와 Value는 항상 정수로 되어있다. 가장 근접한 Key란 두 수의 차이가 가장 작은 Key를 의미한다. 또한, 정보의 정확성을 위해 두 수의 차이가 K보다 큰 경우는 Key로 인정하지 않기로 하였다.

 프로젝트 베끼기의 달인 승균이는 데이터베이스 시간에 JBNU를 모방하기로 했다. 그러나 준하는 전설이기 때문에 그가 만든 프로그램은 찾을 방법이 없었고, 하는 수 없이 같은 조원인 당신에게 맡기려고 한다.

 JBNU의 초기 데이터 상태가 주어질 때, 데이터 추가, 수정 및 검색을 지원하는 프로그램을 작성해보자.

 

[입력]

 첫 줄에는 초기 데이터의 개수인 N(1≤N≤100,000) 과 명령 횟수인 M(1≤M≤100,000), 가장 근접한 Key까지의 거리의 제한인 K(1≤K≤10,000)가 주어진다.

입력의 둘째 줄부터 N개의 줄에는 초기 데이터인 Key와 Value 값이 주어진다. 모든 Key와 Value는 1,000,000,000 이하의 음이 아닌 정수이다. 같은 Key를 갖는 데이터는 없다.

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

• 1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다.
• 2 Key Value : 해당 Key로 검색된 데이터를 Value로 변경한다. 조건을 만족하는 유일한 Key가 없는 경우 무시한다.
• 3 Key : 해당 Key로 검색된 데이터를 출력한다. 조건을 만족하는 Key가 없는 경우 -1을 출력한다. 만약 해당하는 Key가 두 개 이상 존재한다면 ?를 출력한다. 모든 출력은 개행을 포함해야 한다.

 

[출력]

 각 줄에 걸쳐 3번 명령에 대한 결과를 출력한다.

 

[예제 입력 1]

5 7 5
1 10
5 20
9 30
15 40
50 50
3 2
2 0 35
3 2
3 7
3 100
1 97 123
3 100

[예제 출력 1]

10
35
?
-1
123

---

풀이

 문제를 보았을 때 우선적으로 생각한 해결 방법은, 단순히 HashMap에 값을 넣고, 이후 근접한 키를 탐색해야 하는 경우에는 반복문을 통해 근접한 키를 찾아내거나 없음에 대한 결과를 반환해서 명령을 처리하면 되겠다 생각했다.

 하지만 그렇게 코드를 작성한 경우 메모리 초과가 발생했는데, 아무래도 시간 초과로 판단된다. 이후 탐색 함수를 좀 더 개선하기 위해 고민을 했는데, 찾아보니 자바 Map의 인터페이스를 구현 클래스이면서 저장된 key, value 쌍을 정렬해 보관하는 TreeMap을 찾았다. 해당 TreeMap의 메소드 중에서 입력받은 키에 대해 근접한 키를 반환해주는 다양한 메소드가 존재했다.

• ceilingKey(): 현재 key 값 이상의 키들 중에서 가장 작은 키 반환
• higherKey(): 현재 key 값 초과의 키들 중에서 가장 작은 키 반환
• floorKey(): 현재 key 값 이하의 키들 중에서 가장 큰 키 반환
• lowerKey(): 현재 key 값 미만의 키들 중에서 가장 큰 키 반환

 앞선 함수들 모두 마땅한 키가 없으면 null을 반환하는데, 문제 해결 상 null에 대한 처리를 더 유연하게 하고자 미리 한계가 되는 값을 넣어 놓은 다음 탐색 결과에 대해 조건문을 통해 각종 처리를 하였다.

public class Main {

    static int N, M, K;
    static TreeMap<Integer, Integer> DB = new TreeMap<>();
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer s = new StringTokenizer(br.readLine());

        N = Integer.parseInt(s.nextToken());
        M = Integer.parseInt(s.nextToken());
        K = Integer.parseInt(s.nextToken());

        DB.put(-2000000001, -1);//null 방지 최소값 삽입
        DB.put(2000000001, -1);//null 방지 최대값 삽입

        for (int i = 0; i < N; i++) {
            s = new StringTokenizer(br.readLine());
            int key = Integer.parseInt(s.nextToken());
            int value = Integer.parseInt(s.nextToken());

            DB.put(key, value);
        }

        for (int i = 0; i < M; i++) {
            s = new StringTokenizer(br.readLine());
            int query = Integer.parseInt(s.nextToken());
            int key = Integer.parseInt(s.nextToken());
            int value;

            if (query == 1) {//명령 1
                value = Integer.parseInt(s.nextToken());
                DB.put(key, value);
            } else if (query == 2) {//명령 2
                value = Integer.parseInt(s.nextToken());
                int nextKey = find(key);

                if (nextKey >= 0) {
                    DB.replace(nextKey, value);
                }

            } else {//명령 3
                int nextKey = find(key);

                if (nextKey == -1) {
                    answer.append("-1\n");
                } else if (nextKey == -2) {
                    answer.append("?\n");
                } else {
                    answer.append(DB.get(nextKey) + "\n");
                }
            }
        }

        System.out.println(answer.toString());
    }

    static public int find(int key) {//없으면 -1, 2개 이상이면 -2 반환
        Integer upKey, downKey;

        if(DB.containsKey(key)){//입력 받은 key에서 바로 존재
            return key;
        }
        else {
            upKey = DB.higherKey(key);//가장 가까운 큰 키
            downKey = DB.lowerKey(key);//가장 가까운 작은 키

            if (upKey - key > K && key - downKey > K) {//둘 다 K 밖
                return -1;
            }else {
                if (upKey - key <= K && key - downKey <= K) {//둘 다 K 안
                    if (upKey - key == key - downKey) {//둘 다 동일한 차이
                        return -2;
                    } else if (upKey - key < key - downKey) {//upKey 쪽이 더 작음
                        return upKey;
                    }else {//downKey 쪽이 더 작음
                        return downKey;
                    }
                }else if(upKey - key > K){//upKey만 범위 밖
                    return downKey;
                }else {//downKey만 범위 밖
                    return upKey;
                }
            }
        }
    }
}

---

결과