[BOJ 백준] 12757번 : 전설의 JBNU

www.acmicpc.net/problem/12757

12757번: 전설의 JBNU

map과 이분탐색을 활용해서 조건에 맞게 푸는 문제이다.

 

8번의 시도 끝에 풀었다.

 

 

문제 해결

문제를 읽어보면 다음과 같은 조건이 있다.

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

1번은 map에 key와 value를 추가하기만 하면 되는 간단한 조건이다.

 

문제는 2번과 3번인데, 조건을 만족하고 key로 검색한 value를 찾기위해 이분탐색을 사용했다. 

 

이분탐색을 편리하게 하기 위해 cpp의 STL 라이브러리에서는 lower_bound(), upper_bound()의 함수를 제공하고, 이 중 lower_bound를 활용했다.

 

하지만 lower_bound를 사용하면 해당 값 "이상" 의 값 중에서 결과만 나오므로 "이하" 의 값을 찾을 수 없다.

이를 해결하기 위해 수로 저장하고 검색하는 map을 하나 더 만들었다.

 

 

왜 "이하"의 값을 찾아야 하는 것일까?

먼저, 예제에 있는 입력과 결과를 보면 "3 7" 을 입력했을 때 출력이 "?" 나왔다. 

우선, "?"은 "3 7" 을 입력했을 때 나온 출력 값이다. "3 7"이 입력되기 직전에 Map에는 이런 식으로 key:value 값이 저장되어 있을 것이다.

• { 1:10, 5:20, 9:30, 15:40, 50:50}
  • "2 0 35" 입력으로 인해 값 변경
  • { 1:35, 5:20, 9:30, 15:40, 50:50 }

7을 검색하면 Map에는 7이 없기 때문에 7과 가장 가까운 값을 확인해야 한다.

• 7에서 2를 더한 9
• 7에서 2를 뺀 5

이렇게 2개가 있다. 그러므로 문제의 조건에 의해 Key로 인정되지 않는다.

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

lower_bound만 사용하면 9만 검색할 수 있고, 5를 검색할 수 없다. 때문에 음수로 된 Map을 한개 더 활용하여 "이하"의 값을 찾는 것이 필요하다.

 

 

 

소스코드

#include <bits/stdc++.h>
#define endl "\n"
#define MAX 10
using namespace std;
map<int, int> m1; // 위쪽으로 더 가까운 값 : key가 양수
map<int, int> m2; // 아래쪽으로 더 가까운 값 : key가 음수
int n, m, k;
int key, val;
int oper;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("input.txt", "r", stdin);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> key >> val;
        m1[key] = val;
        m2[-key] = val;
    }
    for (int i = 0; i < m; i++) {
        cin >> oper >> key;
        if (oper == 1) {  // 입력
            cin >> val;
            m1[key] = val;
            m2[-key] = val;
        }        
        auto upper = m1.lower_bound(key); 
        auto lower = m2.lower_bound(-key);        
        int up_diff = abs(upper->first - key); // "이상"의 값과의 거리
        int low_diff = abs(key + lower->first); // "이하"의 값과의 거리
        if (oper == 2) {  // 변경
            cin >> val; 
            if (up_diff < low_diff) {  // 위쪽이랑 더 가까움
                if (up_diff <= k) {
                    upper->second = val;
                    m2[-(upper->first)]=val;        
                }
            } 
            if(up_diff > low_diff) {  // 아래쪽이랑 더 가까움
                if (low_diff <= k) {
                    lower->second = val;
                    m1[-(lower->first)] = val;
                }
            }
        } 
        if(oper==3) {  // 출력          
            if (upper->first != -lower->first && up_diff == low_diff) {  // 중복 키
                cout << "?" << endl;
            } 
            else if(up_diff>k && low_diff>k) cout<<"-1"<<endl; // 범위 초과
            else if (up_diff < low_diff) {  // 위쪽이랑 더 가까움               
                cout << upper->second << endl;                                   
            }
            else {  // 아래쪽이랑 더 가까움               
                cout << lower->second << endl;               
            }
        }        
    }
    return 0;
}