BOJ 20551번: Sort 마스터 배지훈의 후계자

문제

---

문제 풀이1 - 시간 초과

1. vector에 차례대로 삽입한 후 오름차순 정렬을 한다.
2. 이분탐색으로 찾고 존재하면 가장 먼저 나타나는 위치를 찾는다.

가장 먼저 나타나는 위치를 for문으로 찾아서 시간 초과가 났다.

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

vector<long long> v;

int binary_search(long long num, int start, int end) {
    int mid = (start + end) / 2;
    if (start > end) { return -1; }

    if (v[mid] == num) {
        for (int i = mid - 1; i >= 0; i--) {
            if (v[i] == num) { mid = i; }
            else { break; }
        }
        return mid;
    }
    else if (v[mid] < num) { return binary_search(num, mid + 1, end); }
    else { return binary_search(num, start, mid - 1); }
}

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

    int n, m, idx;
    long long num;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end()); 

    for (int i = 0; i < m; i++) {
        cin >> num;
        idx = binary_search(num, 0, n - 1);
        cout << idx << '\n';
    }

    return 0;
}

---

문제 풀이2 - 맞았습니다!

1. vector에 차례대로 삽입한 후 오름차순 정렬을 한다.
2. 이분탐색으로 찾고 존재하면 범위를 왼쪽으로 하나씩 좁혀가며 숫자가 더 나오지 않을 때까지 이분탐색한다.

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

// 이분탐색으로 찾고 찾아내면 가장 먼저인 위치를 찾아야함
// 없을 때까지 이분 탐색

vector<long long> v;

int binary_search(long long num, int start, int end) {
    int mid = (start + end) / 2;
    if (start > end) { return -1; }

    if (v[mid] == num) { // 찾으면 더 없을 때까지 이분 탐색
        int temp = mid;
        while (true) {
            temp = binary_search(num, 0, temp - 1);
            if (temp == -1) { break; } // 존재하지 않으면 끝
            else { mid = temp; }
        }
        return mid;
    }
    else if (v[mid] < num) { return binary_search(num, mid + 1, end); }
    else { return binary_search(num, start, mid - 1); }
}

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

    int n, m, idx;
    long long num;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < m; i++) {
        cin >> num;
        idx = binary_search(num, 0, n - 1);
        cout << idx << '\n';
    }

    return 0;
}

이분탐색의 이분탐색

문제 풀이2의 시간 복잡도

• 이분탐색의 시간복잡도: O(logN)
• for문의 시간복잡도: O(N)
• sort()의 시간복잡도: O(NlongN)

시간복잡도는 어떻게 구하는거지ㅜㅜ