글 읽기 - 이중 우선순위 큐 질문 하나 할께요

poia0304 8년 전 0

찾아봤는데 우선순위큐는 힙으로 구현하는 거라 되있었긴 한데..

전 그냥 우선순위큐 안만들고도 배열로 짤 수 있을 것 같길래 시도 해봤는데요 자꾸 시간초과가 뜨네요...ㅠ

배열을 설정해놓고 insert할때 제일 마지막에 넣고 바로 앞과 비교해서 배열이 정렬되도록 짰는데요

Delete와 insert는 실제로 없애지 않고 index(start,end)로 구분했습니다.

저기서 수행시간을 고치면 풀 수 있는건지 아니면 접근방법이 잘 못됬는지 알고 싶습니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

long long arr[2000000];

int main()
{
    int times;
    int opNum;
    char op = 0;
    long long num;
    long long val = 0;
    int cnt = 0;
	int start = 0, end = 0;
	scanf("%d",&times);
	for (int i = 0; i < times; ++i) {
		start = end = 0;
		scanf("%d",&opNum);
		for (int j = 0; j < opNum; ++j) {
			scanf("%c", &op);
			scanf("%c %lld",&op,&num);
			switch (op) {
			case 'I':
				arr[end] = num;
				++end;
				cnt = end;
				for (;cnt - 2 >= 0 && min(arr[cnt - 1], arr[cnt - 2]) == arr[cnt - 1];) {
					swap(arr[cnt - 1], arr[cnt - 2]);
					--cnt;
				}
				break;
			case 'D':
				if (num == -1) {
					if (start < end) { ++start; }
					break;
				}
				else {
					if (start < end) { --end; }
					break;
				}
			}
		}
		if (start >= end) {
			cout << "EMPTY" << endl;
		}
		else {
			cout << arr[end-1] << " " << arr[start] << endl;
		}
	}
	return 0;
}

yukariko 8년 전 0

우선순위 큐에 힙을 쓰는 이유는

가장 우선순위가 높은 요소를 로그시간만에 찾을 수 있으면서, 삽입, 삭제도 로그시간에 해결되기 때문입니다.

위 소스와같은 방법으로 풀게 되면 복잡도가 선형시간이 되기 때문에 시간초과가 뜨는것으로 생각됩니다.

poia0304 8년 전 0

@yukariko

넵..감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

이중 우선순위 큐 질문 하나 할께요

poia0304 8년 전 0

yukariko 8년 전 0

poia0304 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말