[백준] BOJ 1655 가운데를 말해요(CPP)

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

1655번: 가운데를 말해요

이 문제를 처음 접근할때 시간 제한이 0.1초인걸 보지 않고 당연히 1초라고 생각하여 N은 100,000이니 시간 복잡도는 O(N logN)이면 풀 수 있겠다는 생각으로 이분탐색의 형식으로 O(logN)으로 Insert함수를 만들고 N회 입력, Insert, 출력을 반복하는 main 함수로 작성하면 되겠다는 안일한 생각으로 접근을 했다. 그러나 vector.insert가 갖는 시간 복잡도를 생각하지 않아시간 초과가 발생하는 코드가 되었다. 그렇게 다음의 코드가 나왔다. 그러나 시간제한이 0.1초 이기 때문에 우선순위 큐로 작성을 해야 한다.

아래의 코드는 각각 우선순위 큐로 작성한 성공 코드와 이분 탐색으로 작성한 실패 코드이다.

반응형

이분탐색

(시간초과 발생 - 아래로 스크롤하면 우선순위 큐로 작성한 코드가 있습니다.)

//
// Created by 임익주 on 2023/03/30.
//
#include "iostream"
#include "vector"

using namespace std;

vector<int> nums;

int nums_Insert(int num){
    if(nums.empty()){
        nums.push_back(num);
        return 0;
    }
    if(num < nums[0]){
        nums.insert(nums.begin(), num);
        return 0;
    }
    int lo = 0, hi = nums.size(), mid;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(num > nums[mid]){
            //lo 변경
            lo = mid;
        }else if(num <= nums[mid]){
            //hi 변경
            hi = mid;
        }
    }
    mid = (lo + hi) / 2;
    if(nums[mid] < num)
        nums.insert(nums.begin() + ((lo + hi) / 2) + 1, num);
    else if(nums[mid] > num)
        nums.insert(nums.begin() + ((lo + hi) / 2), num);
    return 0;
}

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

    int n, num;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> num;
        nums_Insert(num);
        cout << nums[i / 2] << "\n";
    }
    return 0;
}

 

시간 복잡도를 맞추기 위해서는 우선순위 큐를 이용해야한다.

우선순위 큐

//
// Created by 임익주 on 2023/03/30.
//
#include "iostream"
#include "vector"

using namespace std;

vector<int> nums;

int nums_Insert(int num){
    if(nums.empty()){
        nums.push_back(num);
        return 0;
    }
    if(num < nums[0]){
        nums.insert(nums.begin(), num);
        return 0;
    }
    int lo = 0, hi = nums.size(), mid;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(num > nums[mid]){
            //lo 변경
            lo = mid;
        }else if(num <= nums[mid]){
            //hi 변경
            hi = mid;
        }
    }
    mid = (lo + hi) / 2;
    if(nums[mid] < num)
        nums.insert(nums.begin() + ((lo + hi) / 2) + 1, num);
    else if(nums[mid] > num)
        nums.insert(nums.begin() + ((lo + hi) / 2), num);
    return 0;
}

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

    int n, num;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> num;
        nums_Insert(num);
        cout << nums[i / 2] << "\n";
    }
    return 0;
}