백준 - 1655 가운데를 말해요

문제 링크입니다 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

단계별 풀기에서 유형은 우선순위 큐로 되어 있는데, 우선순위 큐로 어떻게 풀어야 할 지 감지 잘 안 잡혔다. 그래서 우선순위 큐가 시간 복잡도 O(logN)을 잡아먹으니까 이분탐색으로 풀어도 될 것같아 이분탐색으로 풀었다.

 

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int N, input;
    scanf("%d", &N);
    vector<int> v;
    vector<int>::iterator iter;
    int len;

    for(int i = 0; i < N; i++) {
        scanf("%d", &input);
        iter = lower_bound(v.begin(), v.end(), input);
        v.insert(iter, input);
        len = v.size() - 1;
        printf("%d\n", v[len / 2]);
    }

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~