글 읽기 - c++ 1655 시간초과 도와주세요 ㅜㅜㅜ

ks0689 1년 전 0

다른 로직이 있을까요...?

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

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

	int num,n;
	cin >> num;

	priority_queue<int, vector<int>, greater<int>> q; // 오름차순 우선순위 큐

	vector<int> arr;

	int size;

	for (int i = 0; i < num; i++) {
		cin >> n;
		q.push(n);
		size = q.size();

		// 짝수
		if (size % 2 == 0) {
			for (int i = 0; i < (size / 2) - 1; i++) {
				arr.push_back(q.top());
				q.pop();
			}
			cout << q.top() << "\n";
			for (int i = 0; i < arr.size(); i++) q.push(arr[i]);
			
			arr.clear();
		}

		// 홀수
		else {
			for (int i = 0; i < (size / 2); i++) {
				arr.push_back(q.top());
				q.pop();
			}
			cout << q.top() << "\n";
			for (int i = 0; i < arr.size(); i++) q.push(arr[i]);

			arr.clear();
		}
	}

	return 0;
}

zenith82114 1년 전 0

이러면 수 1개당 size만큼 시간이 걸립니다.

우선순위 큐를 하나 더 써서 수 1개당 상수 시간으로 줄일 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 1655 시간초과 도와주세요 ㅜㅜㅜ

ks0689 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말