[C++] IF문 좀 대신 쎠줘 (19637번)

IF문 좀 대신 써줘

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

1024 MB

5741

1955

1552

35.515%

문제

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.

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

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

입력

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 

N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

출력

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

---

문제풀이

칭호가 비 내림 차순으로 주어진다.

처음엔 map을 쓰면 어떻게 될까 생각해 봤지만, 결국엔 탐색을 해야한다. 맨 앞이나 맨 뒤부터 반복하며 하나하나 탐색하는 방법 밖에 없는 것이다.

이 문제는 정렬이 되어있다. 정렬이 되어 있을 경우 탐색하는 방법중 하나는 바로 이분 탐색이다. log(n)의 시간이면 된다.

m개를 찾아야 하므로 총 시간 복잡도는 mLOG(m)이므로 문제를 푸는 데에는 충분한 시간 복잡도다.

 

문제 조건에, 해당하는 칭호가 여러개일 경우 먼저 입력받은 것을 한다고 했다. 여러개일 경우는 입력받은 전투력의 상한 값이 같은 상황밖에 없다. 즉 이전에 입력받은 전투력과 같은 칭호는 그냥 저장하지 않고 넘어가면 된다.

 

배열을 두개 쓰던, pair를 쓰던 그건 자유다. 어떻게든 칭호와 전투력을 매핑하여 저장한 뒤, 입력받은 값을 이용해 이분탐색을 시작하면 된다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<pair<string, int>> v;
    v.reserve(100000);
    string s;
    int a;
    cin >> s >> a;
    v.push_back({s, a});
    for(int i=1; i<n; i++) {
        cin >> s >> a;
        if(v.back().second == a) continue;
        v.push_back({s, a});
    }

    for(int i=0; i<m; i++) {
        int power;
        cin >> power;
        int low = 0;
        int high = v.size()-1;
        int middle = (low+high)/2;
        while(low < high) {
            if(v[middle].second < power) {
                low = middle + 1;
            } 
            else if(v[middle].second > power) {
                high = middle - 1;
            }
            else break;
            middle = (low+high)/2;
        }
        if(v[middle].second >= power) {
            cout << v[middle].first << "\n";
        }
        else {
            cout << v[middle+1].first << "\n";
        }
    }
    return 0;
}

 

 

vector

vector를 쓰는 경우 reserve()를 사용해 주는 것이 좋다고 이번 문제를 풀면서 깨달았다. vector는 미리 공간을 잡고 있다가, 공간을 모두 사용하면 크기를 2배 늘려 재할당하는 작업을 진행한다. 이는 n의 시간 복잡도가 걸리지만, 통상적으로 이 행위가 발생하는 경우가 n번중 1번이므로 시간 복잡도는 1로 본다. 하지만 공간을 많이 사용한다. 재 할당이 일어나기 때문이다. 그러므로 reserve를 해주지 않고 push_back을 해줄경우, 재할당이 일어나며 메모리를 많이 사용하게 된다. 

또 reserve를 해주더라도 size에는 영향을 미치지 않으니 걱정 말자.

위는 reserve를 사용한 것, 아래는 사용하지 않은 것이다.