[백준 19637] - IF문 좀 대신 써줘(이분탐색) C++

문제

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

19637번: IF문 좀 대신 써줘

접근방법

이분탐색이다.

 

이분탐색을 할 때 중요한 포인트는

오른쪽으로 이동할 때, mid+1을 해주고

같은 값(정답이 될 수 있는 값)일 때는 왼쪽으로 이동해주는 것이라고 생각한다.

 

mid = (left + right) / 2이므로 left와 right이 이어지는 숫자인 경우,

항상 mid는 left에 위치하기 때문에,

여기서 만약 정답이 left에 있는 경우는 right = mid를 해주면 자연스럽게 다음 함수에서 left == right가 되고,

만약 정답이 right에 있는 경우, left = mid + 1을 해주면 자연스럽게 다음 함수에서 left == right가 될 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define _FOR(i, s, n) for (int i=s;i<(n);++i)
#define FASTER ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 987654321

int n, m;
vector<pair<string, int>> condition;

int binary_search(int num, int left, int right) {
    if (left == right) {
        return left;
    }
    int mid = (left + right) / 2;
    if (num > condition[mid].second) {
        return binary_search(num, mid+1, right);
    } else if (num <= condition[mid].second) {
        return binary_search(num, left, mid);
    } 
    return left;
}

int main() {
    FASTER
    cin >> n >> m;
    while(n--) {
        string temp; int num;
        cin >> temp >> num;
        condition.push_back({temp, num});
    }
    while(m--) {
        int num;
        cin >> num;
        int index = binary_search(num, 0, (int)condition.size()-1);
        cout << condition[index].first << '\n';
    }

    return 0;
}

결과

 

개선할 점

처음 이분탐색 문제인지 모르고 풀었다가 시간초과를 받았다.

 

문제를 다시보니 입력값이 큰데다 O(nm)만큼 돌아야하기 때문에 시간초과가 날만했다.

 

그래서 다시 이분탐색으로 돌렸는데, 또 시간초과가 나서 나는 어리둥절..

why?

왜 시간 초과가 났는지 아무리봐도 모르겠다. 내 코드는 괜찮은거 같은데..

 

알고보니 cin, cout 때문이었다.. 하 이놈의 cin, cout때문에 여태 얼마나 시간을 날렸는 지 모른다.

 

만만해보이는 문제일수록 문제 시간복잡도 잘 볼것.

cin, cout, '\n' 항상 신경쓸 것.

 

기억하자.