[BOJ/C++] IF문 좀 대신 써줘(19637번)

1. 개요

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

19637번: IF문 좀 대신 써줘

1-1. 설명

밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려 한다. 예를 들면 세 개 칭호가 존재하고 전투력에 따른 조건이다

if power <= 10000
 print WEAK
else if power <= 100000
 print NORMAL
else if power <= 1000000
 print STRONG

혼자 게임 개발하느라 매우 바쁜 밀리를 대신해 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫줄에 칭호의 개수 N과 칭호를 출력해야 하는 캐릭터 개수 M이 빈칸을 사이에 두고 주어짐

 - N과 M은 1이상 100,000 이하 자연수

 - 둘째 줄부터 N개 줄 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하 영어 대문자로만 구성된 문자열이 주어짐

 - 해당 칭호의 전투력 상한값을 나타내는 정수 또한 주어지며 이는 10^9 이하

 - N+2번째 줄부터 M개 줄에는 각 캐릭터 전투력을 나타내는 음이아닌 정수가 주어짐

---

2. 구현

2-1. 풀이

단순히 반복문으로 풀면 시간 초과가 날것이 눈에 보였다. 이분 탐색을 통해서 풀면 될 것 같아, 이를 이용해 해결하였다. 여기서 명심해야할 점은 우리는 하나의 값을 찾는 것이 아닌, 범위를 찾는 것이므로 이 점에 유의하여 구현해야 한다. 단순히 값에 초점을 맞추다보니 자꾸 출력초과가 떠서 살짝 애를 먹었다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 100000;

struct Title {
    int num;
    string name;
};

Title titles[MAX_NUM];
int target;

Title binarySearch(int val, int first, int last);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, num;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> titles[i].name >> titles[i].num;
    }

    for (int i = 0; i < M; i++) {
        cin >> num;
        Title result = binarySearch(num, 0, N - 1);
        cout << result.name << "\n";
    }

    return 0;
}

Title binarySearch(int num, int first, int last) {
    if (first <= last) {
        int mid = (first + last) / 2;
        if (num <= titles[mid].num) return binarySearch(num, first, mid - 1);
        else return binarySearch(num, mid + 1, last);
    }
    else return titles[first];
}