[백준, C++] 19637 - IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

 

문제 분석

입력으로 주어지는 N과 M은 최대 10^5이다. 만일 하나하나 완전탐색으로 푼다면 O(NM)이 걸릴 것이다. 이는 10^10 ... 이니까 어느 정도일까. 계산기로 쳐보니까 100억 정도에 해당한다. 시간 제한이 1초라서 완전탐색으로 푼다면 시간 초과가 날 것이다.

 

어떻게 풀어야 시간 내로 풀 수 있을까. 어떤 값을 빠르게 찾아내는 방법. 이분 탐색만한 게 없다고 생각했다.

 

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

struct Title {
    int value;
    string title;

    Title(int value, string title) {
        this->value = value;
        this->title = title;
    }
};

int n, m;
string title;
int value;
vector<Title> vec;

string findTitle(int value) {
    int left = 0;
    int right = n - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;

        if (vec[mid].value >= value) {
            right = mid - 1;
        } else if (vec[mid].value < value) {
            left = mid + 1;
        }
    }

    if (vec[mid].value < value) {
        return vec[mid + 1].title;
    }
    return vec[mid].title;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> title >> value;
        vec.push_back(Title(value, title));
    }
    for (int i = 0; i < m; i++) {
        cin >> value;
        cout << findTitle(value) << "\n";
    }

    return 0;
}

 

코드 설명

전투력을 value, 칭호를 title이라는 변수명으로 다룬다. 전투력과 칭호를 묶어 구조체 Title로 관리한다.

 

입력은 문제 본문의 입력 설명에서 비내림차순으로 주어진다고 했기 때문에 별도의 정렬은 하지 않았다. 만일 비내림차순이 아니라 마구잡이었다면 compare 함수를 직접 만들어서 구현해야 했을 것이다(compare 함수를 직접 만드는 건 익숙해지지가 않는다).

 

이 문제의 핵심은 이분 탐색의 구현이다. lower_bound를 사용해 빠르게 찾아낼 수도 있지만, 평소 알고리즘의 여러 종류 중에서 이분 탐색에 대한 막연한 공포 (?) 가 있었기 때문에 직접 이분 탐색 메서드를 구현해야겠다고 생각했다.

 

이분 탐색을 처음 공부했을 때, 뭔가 이상하게 공부한 것 같다. 컬렉션 내에는 값의 중복이 없고, 이분 탐색으로 찾고자 하는 값은 반드시 컬렉션 안에 있다 ... 뭐 이런 식으로 가정하고 이분 탐색 과정을 이해했다보니 이 문제를 처음 접했을 때 막연했다.

 

문제 본문의 출력 설명을 보면 '출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다' 라고 되어있다. 즉, 컬렉션 안에 중복되는 value가 있을 수 있다는 말이었다. 이 말인즉슨 이분 탐색 중 타겟 값을 가진 인덱스를 찾았다 해도 바로 리턴하면 안 된다는 뜻이었다.

 

아이패드를 펴고 ... 조금 더 찬찬히 생각을 해보니 일반적인 이분 탐색과 비슷했다. 다만 vec[mid].value == value 일 때 "찾았다 !!" 하고 방심하면 안 되고, mid 직전의 값들도 확인해야 한다는 점이 달랐다. 왜냐면 vec[mid - 1].value 역시 value와 같을 수 있기 때문이었다.

 

findTitle() 메서드는 while문에 break가 없다. 그러니까, while문을 다 끝낸 후의 mid는 찾고자 하는 value보다 "작거나 같은" value의 인덱스이다. 그래서 while문을 끝내고 분기 처리를 한 번 더 해야한다. 만일 vec[mid].value가 찾고자 하는 value와 같다면(ex - value = 10000, vec[mid].value = 10000) vec[mid].title을 출력하면 된다. 하지만 vec[mid].value가 찾고자 하는 value보다 작다면(ex - value = 10000, vec[mid].value = 9999) vec[mid]의 다음인 vec[mid + 1].title을 출력해야 한다. 왜냐면 칭호는 전투력 상한값으로 구분되기 때문이다.

 

헷갈렸던 부분인데, 만일 mid + 1이 out of range이면 어떡하지 하는 생각을 했다. 근데 문제 본문의 입력 설명에 "해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다"라고 되어있다. 오늘도 깨닫는다. 문제를 잘 읽자.